4.23.9 — Maximum Product Subarray

LeetCode 152 · Medium · ★ Blind 75

The problem

Return the largest product of any contiguous subarray.

[2,3,-2,4]    →  6      ([2,3])
[-2,0,-1]     →  0      ([0] — the only non-negative option)
[-2,3,-4]     →  24     (the whole array: -2 × 3 × -4)

Why the obvious approach breaks

For sums, Kadane's algorithm works: carry the best sum ending here, and reset when it goes negative. The rule is that a negative running total can only hurt.

Multiplication breaks that rule. A very negative running product is not useless — one more negative number turns it into a very large positive one. The third example shows it: -2 × 3 = -6 looks terrible, and then -6 × -4 = 24 is the answer.

So the worst value so far is a candidate for the best value next.

Carry both the maximum and the minimum product ending here.

That is the whole solution, and it is the general lesson: when an operation can flip an ordering, track both ends.

The pattern

At each position, the best product ending here is one of three things:

• nums[i] alone — start fresh here;
• nums[i] × best_so_far — extend the best run;
• nums[i] × worst_so_far — extend the worst run, which a negative flips into the best.

And symmetrically for the worst.

\text{best}_i = \max(n,\ n \times \text{best}_{i-1},\ n \times \text{worst}_{i-1})

\text{worst}_i = \min(n,\ n \times \text{best}_{i-1},\ n \times \text{worst}_{i-1})

Including nums[i] on its own is what handles a zero: after a zero, both running values reset to the current number rather than staying stuck at 0.

The solution

Python

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        best = worst = answer = nums[0]

        for n in nums[1:]:
            candidates = (n, n * best, n * worst)
            best, worst = max(candidates), min(candidates)     # compute together
            answer = max(answer, best)

        return answer

TypeScript

function maxProduct(nums: number[]): number {
  let best = nums[0], worst = nums[0], answer = nums[0];

  for (let i = 1; i < nums.length; i++) {
    const n = nums[i];
    const a = n, b = n * best, c = n * worst;
    best = Math.max(a, b, c);
    worst = Math.min(a, b, c);
    answer = Math.max(answer, best);
  }

  return answer;
}

Compute best and worst from the same snapshot. If you assign best first and then use it while computing worst, you are mixing the new value with the old and the answer is wrong. Building the three candidates first, or using simultaneous assignment, avoids it. This is the bug in this problem, and it fails on inputs with an odd number of negatives.

All three variables start at nums[0], which handles a single-element array and gives the loop something to extend.

answer is tracked separately from best, because the best subarray may have ended earlier — the same "return one thing, record another" idea as 4.14.3 Diameter.

Trace

[-2, 3, -4]

n	candidates	best	worst	answer
start		−2	−2	−2
3	3, 3×−2=−6, 3×−2=−6	3	−6	3
−4	−4, −4×3=−12, −4×−6=24	24	−12	24

The 24 comes from worst × n, which is precisely why the minimum has to be carried.

Complexity

O(n) time, O(1) space.

The alternative that is worth knowing

There is a neat solution based on counting negatives, and it explains why the answer looks the way it does.

Split the array at every zero, since a zero can never be inside the answer. Within a segment, if the number of negatives is even, the whole segment is the answer. If it is odd, you must drop one negative — and the only two candidates are the leftmost negative or the rightmost one, because dropping either leaves an even count.

So: for each segment, compare the product from just after the first negative to the end, against the product from the start to just before the last negative.

The same O(n), and it makes the structure of the answer visible in a way the DP does not. Say it if asked "why does tracking the minimum work" — it is the intuition behind the mechanics.

Where this goes next

• Maximum Subarray (Kadane's) — the additive version, where one running value is enough because negatives cannot help. 4.26.1.
• Maximum Product of Three Numbers — the same "a negative can help" idea without a subarray, so it is the two smallest negatives times the largest positive, versus the three largest.
• Best Time to Buy and Sell Stock with a cooldown — a different reason to carry several values: several states rather than several extremes. 4.24.

The general lesson: if an operation can turn the worst into the best, one running value is not enough. That is true for multiplication with negatives, and for any non-monotonic combining function.

What the interviewer will push on

"Why does Kadane's not work directly?" Negatives. A very negative product is a candidate for the maximum after one more negative.

"Why track the minimum?" Same answer, stated as the mechanism.

"What do zeros do?" They reset both running values, which the n on its own in the candidate list handles.

"What is the bug people write?" Updating best before computing worst. Say it before they ask.

"Can you explain the answer without DP?" The even-or-odd negative count argument.

One thing to volunteer: state the reason for carrying two values before writing any code. "Multiplication by a negative swaps the maximum and the minimum, so I have to carry both." One sentence, and the code follows from it.

Next: 4.23.10 Word Break — splitting a string into valid pieces, where the pieces have no fixed length.