Using Dynamic Programming for Maximum Product Subarray

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 value nums[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.