LeetCode 152 – Maximum Product Subarray

Maximum Subarray with multiplication instead of addition, and the change is much bigger than it looks. Kadane works for sums because adding a number moves the running total in a predictable direction. Multiplying does not: the worst prefix so far can become the best one in a single step, so tracking one value is not enough.

The problem

Find the contiguous subarray with the largest product and return that product. The subarray must be non-empty.

[2,3,-2,4]      -> 6      [2,3]
[-2,0,-1]       -> 0      the best is the single 0
[-2,3,-4]       -> 24     the WHOLE array: two negatives cancel
[-2]            -> -2
[0,2]           -> 2
[2,-5,-2,-4,3]  -> 24     [-5,-2,-4,3] has three negatives, so [-2,-4,3]

[-2,3,-4] is the example to hold onto. The best subarray includes a negative at each end, and no algorithm that only tracks the running maximum will find it — at index 1 the best product is 3, and the answer needs the -2 that looked worthless.

Why one variable fails

[-2, 3, -4]

running max only:
  i=0   max = -2
  i=1   max = max(3, -2*3) = 3        the -2 is discarded
  i=2   max = max(-4, 3*-4) = -4      answer reported: 3   WRONG

The -6 that was thrown away at index 1 is exactly what produces 24 at index 2. A large negative is not a bad prefix — it is a latent good one, waiting for another negative.

So carry both: the best product ending here and the worst product ending here. The worst exists solely so that a future negative can flip it into the best.

curMax = max(x, prevMax * x, prevMin * x)
curMin = min(x, prevMax * x, prevMin * x)

All three candidates appear in both lines. x alone is "start fresh here", which is what handles a zero — the run resets rather than being annihilated forever.

The assignment order trap

curMin needs the old curMax. Compute curMax first and assign it, and the second line silently uses the new value:

curMax = max(x, curMax * x, curMin * x);
curMin = min(x, curMax * x, curMin * x);   <- curMax is already the NEW one

Save the previous maximum in a temporary, or compute both into temporaries and assign together. This is the same class of bug as the two-variable rotation in Climbing Stairs, and it is the one mistake that survives casual testing — it happens to give the right answer on arrays with no sign changes.

Java

class Solution {
    public int maxProduct(int[] nums) {
        int best = nums[0];
        int curMax = nums[0], curMin = nums[0];

        for (int i = 1; i < nums.length; i++) {
            int x = nums[i];
            int prevMax = curMax;          // curMin needs the OLD max, not the new one

            // "x alone" is what lets a zero reset the run instead of killing it.
            curMax = Math.max(x, Math.max(prevMax * x, curMin * x));
            curMin = Math.min(x, Math.min(prevMax * x, curMin * x));

            best = Math.max(best, curMax);
        }

        return best;
    }
}

best is seeded from nums[0], not 0 — for the same reason as Maximum Subarray. An all-negative array of odd length must return its least-bad single element, and a zero seed would return 0 for a subarray that does not exist.

LeetCode guarantees every prefix product fits in a 32-bit int. Worth saying you checked, because products overflow far faster than sums and the guarantee is doing real work here.

Python

class Solution:
    def maxProduct(self, nums: list[int]) -> int:
        best = cur_max = cur_min = nums[0]

        for x in nums[1:]:
            candidates = (x, cur_max * x, cur_min * x)
            cur_max, cur_min = max(candidates), min(candidates)   # both from the OLD values
            best = max(best, cur_max)

        return best

Building the three candidates once and unpacking a tuple assignment removes the ordering trap entirely: the whole right-hand side is evaluated before either name is rebound, so there is no stale value to get wrong. It also says plainly that both lines choose from the same three options.

Complexity

	Time	Space
Two rolling values	`O(n)`	`O(1)`
All subarrays	`O(n²)`	`O(1)`

One pass, two extra variables. There is a neat alternative — sweep the array forwards and backwards taking running products and resetting on zeros — which is also O(n) and exploits the fact that a maximum product always starts or ends at an array boundary or a zero. It is a cute observation and harder to justify on the spot; prefer the DP.

Zeros deserve a sentence

A zero forces both curMax and curMin to 0, which is correct: any subarray containing it has product 0. The x-alone candidate is what lets the next element start a fresh run rather than being multiplied by that 0 forever.

And 0 may itself be the answer — [-2,0,-1] returns 0 — so the zero is not merely a separator, it is a candidate like any other. Both facts fall out of the recurrence without a special case, which is worth pointing at.

The pattern

"Track the extreme in both directions because the operation can flip sign" recurs whenever the combining operation is not monotonic. It is why 53 needs one variable and this needs two. Maximum Product of Three Numbers (628) is the same insight without the subarray structure: the answer is either the three largest or the two smallest times the largest.

The general question to ask of any Kadane-shaped problem: can a bad prefix become good? If yes, carry the bad one too.

What the interviewer is checking

That you find [-2,3,-4] or similar and show one variable failing.
Tracking the minimum as well as the maximum, and why.
The x-alone candidate, and what it does for zeros.
The assignment-order trap — curMin needs the old curMax.
best seeded from nums[0], not 0.
A single element, all negatives, and an array containing zeros.
That you notice products overflow much sooner than sums.