Maximum Product Subarray: Why You Track a Min and a Max
Find the largest-product contiguous subarray in O(n) by tracking both a running max and a running min, so a negative times a negative can flip into the answer.
This article has an interactive companion
Don't just read it — step through it interactively, one state change at a time.
Maximum Subarray (the sum version) has one clean trick: keep a running best and reset when it turns negative. Maximum Product Subarray looks like the same problem with + swapped for * — but that one swap breaks the trick completely.
The reason is a single arithmetic fact: a negative times a negative is positive. The worst running product you have — a big negative number — is exactly one negative sign away from becoming the best. So the smallest product you've seen is not garbage to throw away. It's a candidate you have to keep.
That is the whole problem, and the whole solution: track two things at once.
The problem
Given an integer array nums, find the contiguous subarray (at least one element) that has the largest product, and return that product.
Input: nums = [2, 3, -2, 4]
Output: 6 // subarray [2, 3] has product 6
Input: nums = [-2, 3, -4]
Output: 24 // the whole array: -2 * 3 * -4 = 24Two things make this harder than the sum version:
- A negative value flips large-positive into large-negative and vice versa, so the running extremes swap roles.
- A zero wipes any running product to 0, cutting the array into independent segments.
The subarray must be contiguous — you cannot skip elements — so this is a single left-to-right scan, not a subset-selection problem.
The brute force baseline
Try every subarray, multiply it out, keep the best product.
function maxProduct(nums) {
let best = -Infinity;
for (let i = 0; i < nums.length; i++) {
let product = 1;
for (let j = i; j < nums.length; j++) {
product *= nums[j]; // extend the subarray [i..j]
best = Math.max(best, product);
}
}
return best;
}The outer loop fixes a start i; the inner loop extends the end j and multiplies incrementally, so each subarray costs O(1) to extend. That's O(n²) total. On a 10⁴-element array that's a hundred million multiplications — correct, but far more work than needed. Every start index re-multiplies a suffix the previous start already touched.
The key insight: carry both extremes forward
Kadane's algorithm for maximum sum keeps one value: the best sum ending at the current index. For products, one value isn't enough, because multiplication doesn't preserve ordering across a sign flip.
Picture the running products ending at index i-1. Say the max ending there is 6 and the min is -12. Now element i arrives:
- If
nums[i] = 4(positive), the new best comes from6 * 4 = 24. The positive scales both extremes without swapping them. - If
nums[i] = -4(negative), the new best comes from-12 * -4 = 48. The minimum became the maximum. If you'd only tracked the max, you would have computed6 * -4 = -24and missed the real answer.
So at every index the new max is the largest of three candidates, and the new min is the smallest of the same three:
candidates = { nums[i], prevMax * nums[i], prevMin * nums[i] }
newMax = max(candidates)
newMin = min(candidates)nums[i] alone is in the set because the best subarray might start fresh at i — that's how a zero or a sign break gets escaped. This is the Kadane's Algorithm variant that carries a running min alongside the running max.
The optimal solution
var maxProduct = function(arr) {
if (!arr || arr.length === 0) return 0;
let maxProdSoFar = arr[0];
let minProdSoFar = arr[0];
let totalMax = arr[0];
for (let i = 1; i < arr.length; i++) {
const current = arr[i];
const prevMax = maxProdSoFar;
maxProdSoFar = Math.max(current, prevMax * current, minProdSoFar * current);
minProdSoFar = Math.min(current, prevMax * current, minProdSoFar * current);
totalMax = Math.max(totalMax, maxProdSoFar);
}
return totalMax;
};Three details carry all the weight:
- Seed with
arr[0], loop from index 1. The subarray must be non-empty, so the first element is the initial best for all three variables. - Snapshot
prevMaxbefore overwriting.minProdSoFarstill needs the old max on the same line, so capturingprevMaxfirst prevents using an already-updated value. - No special case for zero. When
currentis 0,currentitself is one of the three candidates, somaxProdSoFarandminProdSoFarboth collapse toward 0 and the chain naturally restarts on the next element. Thecurrentterm does the reset for free.
Walkthrough
Trace nums = [-2, 3, -4]. The answer is 24, and it only appears because the running min carried a negative forward.
| i | current | prevMax | maxProdSoFar = max(current, prevMax·cur, prevMin·cur) | minProdSoFar = min(...) | totalMax |
|---|---|---|---|---|---|
| — | seed | — | -2 | -2 | -2 |
| 1 | 3 | -2 | max(3, -6, -6) = 3 | min(3, -6, -6) = -6 | 3 |
| 2 | -4 | 3 | max(-4, -12, 24) = 24 | min(-4, -12, 24) = -12 | 24 |
At i = 2 the negative -4 multiplies the running min -6 to produce 24, which beats every other candidate. If the algorithm had thrown minProdSoFar away after step 1, the best it could compute here would be 3 * -4 = -12, and it would return 3 — wrong. Keeping the min is the entire point.
Complexity
| Approach | Time | Space | Why |
|---|---|---|---|
| Brute force | O(n²) | O(1) | every start index re-multiplies a growing suffix |
| Running min/max | O(n) | O(1) | one pass, three constant-time comparisons per element |
The optimal scan touches each element once and stores exactly three numbers regardless of input size — constant extra space. The two Math.max/Math.min calls per iteration are O(1), so the total is a clean linear pass.
Common mistakes
- Tracking only the maximum. This is the classic bug. Without
minProdSoFar, a negative element can never flip into the answer, and inputs like[-2, 3, -4]return the wrong result. - Updating min using the already-updated max. You must read
prevMax(a snapshot) when computingminProdSoFar. If you overwritemaxProdSoFarfirst and then reuse it, both lines share a corrupted value. - Forgetting
currentas a standalone candidate. Dropping the barecurrentterm breaks zero resets and sign-break restarts, because nothing lets a subarray begin fresh ati. - Seeding max/min to 0 instead of
arr[0]. Seeding at 0 silently forbids all-negative answers like[-3], where the correct output is-3, not0.
Where this pattern shows up next
The "carry a small amount of running state forward and take a max at each step" shape is the backbone of one-dimensional DP:
- Min Cost Climbing Stairs — the same running-state idea, minimizing cost instead of maximizing a product.
- House Robber — carry two values (rob / skip) forward and take the best at each index.
- House Robber II — the circular version, solved by running the linear scan twice.
- Coin Change — DP over amounts, where each state is the best of several transitions.
You can also step through Maximum Product Subarray interactively to watch the running min and max swap places the instant a negative arrives.
FAQ
Why do you track a minimum product for a maximum problem?
Because multiplying by a negative number swaps the roles of the smallest and largest running products. The most negative product you've built is one negative element away from becoming the most positive. If you discard it, you can't recover the answer for inputs like [-2, 3, -4], whose best subarray product (24) comes from a running minimum flipping sign. Tracking both extremes is what makes the linear scan correct.
How does this handle zeros in the array?
Zeros are handled implicitly. When the current element is 0, it becomes one of the three candidates in both the max and min comparisons, so both running products collapse to 0. On the next element, the standalone current term lets a brand-new subarray start after the zero. There's no explicit if (nums[i] === 0) reset needed — the Math.max(current, ...) structure does it automatically.
What is the time and space complexity?
O(n) time and O(1) space. The array is scanned exactly once, and each element requires a constant number of multiplications and comparisons. Only three numbers are stored — the running max, the running min, and the global best — no matter how large the input, so the extra space never grows.
How is this different from Kadane's maximum subarray sum?
Kadane's sum algorithm keeps a single running best, because addition preserves ordering: adding any value to a larger sum stays larger. Multiplication does not — a negative multiplier reverses ordering — so one running value isn't enough. The product version keeps two (a running max and a running min) and considers three candidates each step. It's a direct extension of Kadane's idea, adapted for sign flips.
Can the answer ever be negative?
Yes. If every element is negative and there's an odd count, like [-3] or [-1, -2, -3] where no even-length all-negative subarray wins, the maximum product can be negative. That's exactly why the three variables are seeded with arr[0] rather than 0 or 1 — the algorithm must be allowed to return a single negative element as the best possible product.
Make it stick: run this one yourself
Don't just read it — step through it interactively, one state change at a time.