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.
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 theg
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
andg
in variablesff
andgg
before they get updated. This is because the newf
andg
will depend on the previous values of bothf
andg
, 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 previousf
, which is the previous maximum product ending at the last element. - The product of the current element
x
and the previousg
, because whenx
is negative andg
is also negative, their product will be positive and can potentially be larger thanf * x
.
- The current element
-
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 previousf
. - The product of
x
and the previousg
.
- The current element
-
It then updates
ans
with the maximum value betweenans
and the newf
. The loop will ensure that by the end,ans
contains the highest product of any subarray withinnums
.
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.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's take a small array to illustrate how the solution approach works. Consider nums = [2, 3, -2, 4]
.
-
Initialize
ans
,f
, andg
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
, andans
at each step. -
At index 1 (
nums[1] = 3
):- Store previous
f
andg
inff
andgg
: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
- Store previous
-
At index 2 (
nums[2] = -2
):- Store previous
f
andg
inff
andgg
: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
- Store previous
-
At index 3 (
nums[3] = 4
):- Store previous
f
andg
inff
andgg
: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
- Store previous
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
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.
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
Recommended Readings
What is Dynamic Programming Prerequisite DFS problems dfs_intro Backtracking problems backtracking Memoization problems memoization_intro Pruning problems backtracking_pruning Dynamic programming is an algorithmic optimization technique that breaks down a complicated problem into smaller overlapping sub problems in a recursive manner and uses solutions to the sub problems to construct a solution
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.
The answer to the example [2, 3, -2, 4] is 6, not 48. I believe 4 should have been replaced with -4.