152. Maximum Product Subarray

Problem Description

The given LeetCode problem is about finding the subarray within an integer array nums that yields the highest product. A subarray is essentially a contiguous part of an array. The key point here is that we are not just looking for the maximum element but the contiguous sequence of elements that when multiplied together give the maximum product. This problem is challenging because the array may contain negative numbers, and a product of two negatives yields a positive, which could potentially be part of the maximum product subarray. The solution must also take into account that the final product has to fit in a 32-bit integer, which sets a defined range of integer values.

Intuition

The intuition behind the solution is to keep track of both the maximum and minimum product at each position in the array as we iterate through it. This is important because a new maximum product can emerge from the multiplication of the current element with the previous minimum product if the current element is a negative number.

To arrive at the solution approach, we need to think about how the sign of an integer (positive or negative) affects the product. The dynamic nature of this problem comes from the fact that including a number in a product might change the maximum or minimum product because of multiplication rules (a positive multiplied by a negative yields a negative, but a negative multiplied by a negative yields a positive).

Therefore, at each step, we have three choices to make for both the maximum and minimum products:

Take the current number itself (which might be beneficial if the current maximum/minimum product held before is less/more beneficial than starting afresh from the current number).
Multiply the current number by the previous maximum product (as usual, to maintain a running product).
Multiply the current number by the previous minimum product (particularly useful when multiplying by a negative number could yield a larger product).

We maintain two variables f and g to keep track of the running 'maximum' and 'minimum' products, respectively, as we iterate through the array. For each new element x, we calculate the new maximum f by choosing the maximum between x, f * x, and g * x. Analogously, we calculate the new minimum g by choosing the minimum between x, f * x, and g * x. Meanwhile, we also maintain a running maximum ans to store the maximum product found so far.

By keeping track of both the maximum and minimum products at each step, we are able to handle the intricacies introduced by negative numbers, ensuring that we can always capture the highest product subarray even when it is formed by turning a negative maximum product positive with another negative number.

Learn more about Dynamic Programming patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Which of these pictures shows the visit order of a depth-first search?

I don’t know

Solution Approach

The solution uses a simple but clever approach leveraging dynamic programming. Instead of keeping a single running product, it keeps track of two products at each iteration - the maximum product and the minimum product up to that point in the array. The algorithm uses three variables:

ans to store the global maximum product of any subarray encountered so far. It is initialized with the first element of the array since the maximum product subarray might just be the first element if all other elements are non-positive.
f to store the maximum product of a subarray ending at the current element. It's like a "local maximum" that is updated at each step.
g to store the minimum product of a subarray ending at the current element. This "local minimum" is crucial as it can turn into the "local maximum" if the current element and the g value are both negative.

The algorithm then iterates through the array starting at the second element (since the first element is already used to initialize the variables). For each element x in nums starting from index 1:

It temporarily stores the previous values of f and g in variables ff and gg before they get updated. This is because the new f and g will depend on the previous values of both f and g, and the calculation of one should not affect the other.
The algorithm updates f by choosing the maximum value among three candidates:
- The current element x itself. This is because the maximum product could start fresh from the current position.
- The product of the current element x and the previous f, which is the previous maximum product ending at the last element.
- The product of the current element x and the previous g, because when x is negative and g is also negative, their product will be positive and can potentially be larger than f * x.
It updates g in a similar manner but chooses the minimum among the same three candidates mentioned above:
- The current element x.
- The product of x and the previous f.
- The product of x and the previous g.
It then updates ans with the maximum value between ans and the new f. The loop will ensure that by the end, ans contains the highest product of any subarray within nums.

By maintaining both f and g at each step, the current element has the flexibility to contribute to either a new maximum or minimum subarray product depending on its value and the current status of f and g. This dynamic behavior allows the solution to effectively handle sequences with negative numbers and track the maximum subarray product accurately.

The reference solution uses this approach efficiently, leading to a time complexity of O(n) since it goes through the array only once, and a space complexity of O(1) since it only uses a constant amount of extra space.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Example Walkthrough

Let's take a small array to illustrate how the solution approach works. Consider nums = [2, 3, -2, 4].

Initialize ans, f, and g with the first element of the array:
- ans = 2
- f = 2
- g = 2
Iterate from the second element to the end of the array, updating f, g, and ans at each step.
At index 1 (nums[1] = 3):
- Store previous f and g in ff and gg:
  - ff = 2
  - gg = 2
- Calculate new f: max(3, 2 * 3, 2 * 3) = max(3, 6, 6) = 6
- Calculate new g: min(3, 2 * 3, 2 * 3) = min(3, 6, 6) = 3
- Update ans: max(ans, f) = max(2, 6) = 6
At index 2 (nums[2] = -2):
- Store previous f and g in ff and gg:
  - ff = 6
  - gg = 3
- Calculate new f: max(-2, 6 * -2, 3 * -2) = max(-2, -12, -6) = -2
- Calculate new g: min(-2, 6 * -2, 3 * -2) = min(-2, -12, -6) = -12
- Update ans: max(ans, f) = max(6, -2) = 6
At index 3 (nums[3] = 4):
- Store previous f and g in ff and gg:
  - ff = -2
  - gg = -12
- Calculate new f: max(4, -2 * 4, -12 * 4) = max(4, -8, 48) = 48
- Calculate new g: min(4, -2 * 4, -12 * 4) = min(4, -8, 48) = -8
- Update ans: max(ans, f) = max(6, 48) = 48

After iterating through the entire array, our ans is 48, which is the highest product of a subarray in nums. This subarray is actually [2, 3, -2, 4] itself, and the maximum product is 2 * 3 * -2 * 4 = 48.

By tracking both the maximum (f) and minimum (g) products at each step and updating the global maximum (ans), we arrive at the correct solution efficiently.

Solution Implementation

1class Solution:
2    def maxProduct(self, nums: List[int]) -> int:
3        # Initialize the maximum product, current maximum, and current minimum.
4        max_product = current_max = current_min = nums[0]
5      
6        # Iterate over the numbers starting from the second element.
7        for num in nums[1:]:
8            # Save the previous step's maximum and minimum.
9            temp_max, temp_min = current_max, current_min
10          
11            # Calculate the current maximum product ending at the current number.
12            # It's the maximum of the current number, product of the current number and previous maximum,
13            # or the product of the current number and previous minimum.
14            current_max = max(num, temp_max * num, temp_min * num)
15          
16            # Calculate the current minimum product ending at the current number.
17            # It's the minimum for the same reason above but will be used to handle negative numbers.
18            current_min = min(num, temp_max * num, temp_min * num)
19          
20            # Update the overall maximum product found so far.
21            max_product = max(max_product, current_max)
22      
23        # Return the maximum product of the array.
24        return max_product
25

1class Solution {
2    public int maxProduct(int[] nums) {
3        // Initialize the maximum, minimum, and answer with the first element.
4        // The max value 'maxProduct' represents the largest product found so far and 
5        // could be the maximum product of a subarray ending at the current element.
6        // The min value 'minProduct' represents the smallest product found so far and 
7        // could be the minimum product of a subarray ending at the current element.
8        // This is required because a negative number could turn the smallest value into 
9        // the largest when multiplied by another negative number.
10        int maxProduct = nums[0]; 
11        int minProduct = nums[0];
12        int answer = nums[0];
13      
14        // Iterate through the array starting from the second element.
15        for (int i = 1; i < nums.length; ++i) {
16            // Store the current max and min before updating them.
17            int currentMax = maxProduct;
18            int currentMin = minProduct;
19          
20            // Update the maxProduct to be the maximum between the current number, 
21            // currentMax multiplied by the current number, and currentMin multiplied 
22            // by the current number. This accounts for both positive and negative numbers.
23            maxProduct = Math.max(nums[i], Math.max(currentMax * nums[i], currentMin * nums[i]));
24          
25            // Update the minProduct similarly by choosing the minimum value.
26            minProduct = Math.min(nums[i], Math.min(currentMax * nums[i], currentMin * nums[i]));
27          
28            // Update the answer if the newly found maxProduct is greater than the previous answer.
29            answer = Math.max(answer, maxProduct);
30        }
31      
32        // Return the largest product of any subarray found.
33        return answer;
34    }
35}
36

1#include <vector>
2#include <algorithm> // Include algorithm header for max() and min() functions
3
4class Solution {
5public:
6    // Function to calculate the maximum product subarray
7    int maxProduct(vector<int>& nums) {
8        // Initialize variables: maxEndHere for the current maximum product,
9        // minEndHere for the current minimum product, and
10        // maxProductOverall for the overall maximum product found.
11        int maxEndHere = nums[0], minEndHere = nums[0], maxProductOverall = nums[0];
12
13        // Iterate through the vector starting from the second element
14        for (int i = 1; i < nums.size(); ++i) {
15            // Store the previous values of maxEndHere and minEndHere
16            int tempMaxEndHere = maxEndHere, tempMinEndHere = minEndHere;
17
18            // Calculate the new maxEndHere by considering the current number itself,
19            // the product of the current number with the previous maxEndHere, and
20            // the product of the current number with the previous minEndHere.
21            // This accounts for the possibility of a negative number times
22            // a negative minEndHere becoming a maximum.
23            maxEndHere = max({nums[i], tempMaxEndHere * nums[i], tempMinEndHere * nums[i]});
24
25            // Similarly, calculate the new minEndHere
26            minEndHere = min({nums[i], tempMaxEndHere * nums[i], tempMinEndHere * nums[i]});
27
28            // Update the maxProductOverall with the maximum value found so far
29            maxProductOverall = max(maxProductOverall, maxEndHere);
30        }
31        // Return the maximum product subarray found
32        return maxProductOverall;
33    }
34};
35

1function maxProduct(nums: number[]): number {
2    // Initialize the max product, min product, and answer all to the first element 
3    // of the array since we will compare these to every other element moving forward.
4    let maxProd = nums[0];
5    let minProd = nums[0];
6    let answer = nums[0];
7
8    // Loop through the array starting from the second element
9    for (let i = 1; i < nums.length; ++i) {
10        // Keep temporary copies of the current max and min products before they get updated.
11        const tempMaxProd = maxProd;
12        const tempMinProd = minProd;
13
14        // Compute the new maxProd by considering the current element,
15        // the product of the current element and the previous maxProd,
16        // and the product of the current element and the previous minProd.
17        // The maxProd can either include the current element by itself 
18        // or include a subarray ending at the current element.
19        maxProd = Math.max(nums[i], tempMaxProd * nums[i], tempMinProd * nums[i]);
20
21        // Compute the new minProd using similar logic to maxProd.
22        // The minProd accounts for negative numbers which could be useful 
23        // if the current element is negative (a negative times a negative is positive).
24        minProd = Math.min(nums[i], tempMaxProd * nums[i], tempMinProd * nums[i]);
25
26        // Update answer with the larger value between the current answer and the new maxProd.
27        // This could be the max product of a subarray up to the current index.
28        answer = Math.max(answer, maxProd);
29    }
30
31    // Return the maximum product of any subarray found in the nums array.
32    return answer;
33}
34

Not Sure What to Study? Take the 2-min Quiz：

Given a sorted array of integers and an integer called target, find the element that equals to the target and return its index. Select the correct code that fills the ___ in the given code snippet.

1def binary_search(arr, target):
2    left, right = 0, len(arr) - 1
3    while left ___ right:
4        mid = (left + right) // 2
5        if arr[mid] == target:
6            return mid
7        if arr[mid] < target:
8            ___ = mid + 1
9        else:
10            ___ = mid - 1
11    return -1
12

1public static int binarySearch(int[] arr, int target) {
2    int left = 0;
3    int right = arr.length - 1;
4
5    while (left ___ right) {
6        int mid = left + (right - left) / 2;
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16

1function binarySearch(arr, target) {
2    let left = 0;
3    let right = arr.length - 1;
4
5    while (left ___ right) {
6        let mid = left + Math.trunc((right - left) / 2);
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16

<=, left, right<, left, right<=, right, left<, right, left

I don’t know

Time and Space Complexity

The time complexity of the given code is O(n) where n is the number of elements in the input list nums. This is because it processes each element exactly once in a single loop.

The space complexity of the code is O(1) because it uses a constant amount of additional space. The variables ans, f, g, ff, and gg do not depend on the size of the input, so the space used does not scale with the size of the input list.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Overview

Basic Data Structures

Basic Algorithms

Overview

Sorted Array

Implicitly Sorted Array

Advanced

Speedrun

Introduction

DFS on Tree

Binary Search Tree

Advanced

Combinatorial Search

Pruning

Additional States

Aggregation and Memoization

Dedup

Additional Practices

Speedrun

Introduction

BFS on Tree

Introduction

Vanilla BFS

Matrix as Graph

Implicit Graph

Directed Graph / Topological Sort

Weighted Graph

Minimum Spanning Tree

Speedrun

Introduction

Same Direction

Opposite Direction

Sliding Window

Prefix Sum

Cycle Finding

Advanced

Speedrun

Introduction

Top K

Moving Best

Multiple Heaps

Introduction

Grid

Dynamic number of subproblems

Interval

Dual-Sequence

Knapsack

Bitmask

Additional Practices

Disjoint Set Union | Union Find

Trie

Data Structure Design

Segment Tree

Interval

Monotonic Stack

Divide and Conquer

Line Sweep

Tree Traversal without Recursion

Greedy

Math

Matrix

Classics

Concepts

Projects

Amazon OA

Microsoft OA

Google OA

Twitter OA

Editorials

152. Maximum Product Subarray

Problem Description

Intuition

Solution Approach

Example Walkthrough

Solution Implementation

Time and Space Complexity

Recommended Readings