Earlier this year, we solved LeetCode 53: Maximum Subarray, which asked us to find the sum of the subarray (contiguous non-empty sequence of elements) with the largest sum. This week, we’ll look at a related problem that asks for the largest product.
Maximum Sum Subarray Review
For the maximum sum subarray problem, the maximum sum at position i
in nums
is:
- The sum at position
i-1
plus the input valuenums[i]
, or - Just the input value
nums[i]
itself.
At each position, we pick the larger of those two options. Once we get to the end of the input array, the solution is the maximum value across all positions.
Maximum Product Subarray
We can use a similar approach for the product version of the problem, with some additional complexity because we’re calculating products rather than sums. For sums, a positive element increases the subarray sum, a zero element doesn’t change it, and a negative element decreases it. For products, we have to consider both the current product and the current element. If the current element is 0
, then the product permanently drops to 0
and never changes. If the current element is 1
, then there is no change to the product. Otherwise, the result is based on the signs of the element and the product. If the signs match (e.g., current product negative and current element negative), then the result is a larger positive value. If the signs don’t match (e.g., current product positive and current element negative), then the result is a value that is larger in magnitude, but negative.
To handle these rules, we’ll use a different memo table design. For Maximum Sum Subarray, we used one dp
array to store the maximum sum at each position. For Maximum Product Subarray, we’ll use two: dpMax
to store the maximum products, and dpMin
to store the minimum products. We need the second array because if nums[i]
is negative, we need to check if we get a maximum positive result when we multiply it with a negative product.
So while we had only two values to evaluate at each position with the sum problem, the product problem requires checking three values:
- The input value
num = nums[i]
. - The maximum product at position
i-1
times num. - The minimum product at position
i-1
times num.
At each position, we update dpMax
with the largest of these three values, and dpMin
with the smallest of the three. At the end, the solution is the largest of all the dpMax
values.
As with Maximum Sum Subarray, we can see from this summary that we only need the current max/min product and the previous max/min product. So we can use $O(1)$ space if we do away with the dp
arrays and just store those values. I’ll show the array solution here.
Solution Intuition
We know that dynamic programming improves the efficiency of a solution by calculating and storing results to be used later. Since we’re looking for the maximum product in this problem, an obvious idea is to use a dp
array where dp[i]
is the maximum product at position i
. But that doesn’t work when the input array contains negative numbers. The solution is to use a second array to store minimum products. We also need to recognize that a minimum product can become a maximum product because of the arithmetic rule of signs (a negative number times a negative number is a positive number).
When we’re designing a dynamic programming solution, we have to look for useful intermediate results to store, and think about how we can use these results to solve the problem more efficiently. Sometimes this will lead to a multidimensional approach, but for this problem we just need two 1D arrays (or a few scalar variables).
Pseudocode
n = length of nums
dpMax = array of size n
dpMin = array of size n
max = dpMax[0] = dpMin[0] = nums[0]
for i from 1 to n-1
num = nums[i]
tryMax = dpMax[i-1] * num
tryMin = dpMin[i-1] * num
dpMax[i] = max(num, tryMax, tryMin)
dpMin[i] = min(num, tryMax, tryMin)
max = max(max, dpMax[i])
return max
References
For the $O(1)$ space approach, see chase1991’s solution. For a prefix product/suffix product approach, see my previous post on this problem, based on lee215’s solution on LeetCode.
Thanks to Daniel Zingaro for suggesting an improvement to this article.
(Image credit: DALLĀ·E 3)
For an introduction to this year’s project, see A Project for 2024.