Maximum Product Subarray
Contiguous subarray with the largest product. Negatives and zeros lurk in the array.
- 1 <= nums.length <= 2 * 10⁴
- -10 <= nums[i] <= 10
- The product of any subarray of nums is guaranteed to fit in a 32-bit integer.
Intuition
Maximum product subarray looks like Kadane's algorithm with multiplication swapped in, and that instinct is almost right — but it breaks in a way worth understanding precisely.
With sums, a larger running total is always at least as useful going forward. With products, that stops being true the moment a negative number appears. Multiplying by a negative inverts the ordering: the most negative running product becomes the largest one, and the largest becomes the most negative.
So discarding the minimum is exactly what loses the answer. Take [-2, 3, -4]. The best product is 24, and it routes through the running value −6, which any max-only tracker would have thrown away as worthless.
The fix follows directly:
- Track both the maximum and the minimum product ending at the current position, because a negative number swaps their roles.
At each element the candidates are the element alone, the element times the previous maximum, and the element times the previous minimum. The new maximum and minimum are the largest and smallest of those three. Starting fresh with the element alone is what handles the subarray beginning here.
One implementation detail: compute both new values from the old pair before assigning either. Overwriting the maximum first and then using it to compute the minimum is a real and easy bug.
Zeros need no special handling. They collapse both candidates toward zero, and the element alone option restarts the window naturally on the next step.
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
Before reading on: price up what the direct approach costs here, then ask what a single cell should mean, and which earlier cells it needs. Aim for O(n) time and O(1) space.
See exactly why plain Kadane fails
With sums, a bigger prefix is always better. With products, a negative number makes the most negative prefix the most valuable. In [-2, 3, -4] the answer 24 routes through −6, which a max-only tracker discards.
Track a maximum and a minimum together
Keep both the largest and smallest product ending at the current index. The minimum is not a curiosity — it is the candidate that becomes the maximum as soon as a negative number arrives.
Consider three candidates per element
For element x, the options are x alone, x * previousMax, and x * previousMin. The new maximum is the largest of the three and the new minimum the smallest. Including x alone is what allows a subarray to start here.
Compute both before assigning either
Store the old maximum in a temporary, or compute both new values in one step. Overwriting the maximum first and then using it for the minimum is a genuine bug that quietly produces wrong answers on mixed-sign inputs.
Update the global answer each step
Compare the running maximum against the best seen so far at every index. The answer may occur anywhere, not only at the end — the same accounting as ordinary Kadane.
Let zeros handle themselves
A zero drives both candidates to zero, and the x alone option restarts the window on the next element. No special case is needed, which is worth checking rather than assuming when writing it.
Cost of the single pass
One traversal keeping two running values gives O(n) time and O(1) space — the same bounds as Kadane's algorithm, with the only addition being the second tracked value.
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.