Maximum Product Subarray
Contiguous subarray with the largest product. Negatives and zeros lurk in the array.
Open on LeetCode ↗Intuition
Kadane's trick almost works, but a negative number flips the world: the smallest (most negative) product so far becomes the biggest after multiplying by a negative. So track two running values — the max AND the min product ending here. Each new element either starts fresh or extends one of them; a zero resets both.
Kadane breaks here because a negative number flips the ranking — today's worst product can become tomorrow's best. So track both extremes. Whenever the operation can reverse order (multiplication with negatives, sign flips), carrying a running minimum alongside the maximum is what repairs the recurrence.
Approach
Why plain Kadane breaks
With sums, a bigger prefix is always better. With products, [-2, 3, -4]: the best answer 24 routes through the most negative prefix −6. Discarding minima loses the answer.
Track a (max, min) pair
For each x: candidates are {x, x·curMax, x·curMin}. New curMax = max of them, new curMin = min of them. A negative x swaps the roles — which is exactly why both are kept.
Answer is the best curMax seen
Update the global answer each step. Zeros make both candidates collapse toward x=0, restarting the window naturally.
Solution & live demo
Common pitfalls
Tracking only the running maximum
cur_max = max(x, x * cur_max) ans = max(ans, cur_max)
cands = (x, x * cur_max, x * cur_min) cur_max, cur_min = max(cands), min(cands)
On [-2, 3, -4] the answer is 24, produced by multiplying two negatives. A max-only recurrence discards the large negative product at each step, so the pair can never recombine. The minimum is a candidate precisely because a later negative promotes it.
Updating the two variables sequentially
cur_max = max(x, x * cur_max, x * cur_min) cur_min = min(x, x * cur_max, x * cur_min)
cands = (x, x * cur_max, x * cur_min) cur_max, cur_min = max(cands), min(cands)
The second line reads the new cur_max, not the previous one, so the minimum is computed against a value from the wrong iteration. Both must be derived from the same snapshot — the tuple assignment guarantees it.
Seeding the extremes at 1 or 0
ans = cur_max = cur_min = 1
ans = cur_max = cur_min = nums[0]
1 is an identity that was never in the array, so a single-element input like [-3] reports 1 instead of -3. A subarray must be non-empty, so the first element is the correct seed.
Edge cases
Answer is that element — 'start fresh at x' candidate covers it.
Both trackers pass through 0 and restart after it.
The min-tracker carries the odd-negative prefix until a second negative flips it positive.