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, a positive element increases the subarray product, a zero element permanently drops it to `0`

, and a negative element increases/decreases it and flips the sign (which could make the result larger or smaller).

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. This is useful 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.

(Image credit: DALLĀ·E 3)

*For an introduction to this year’s project, see A Project for 2024*.