Maximum Product Subarray
WHAT IT SAYS
Find the largest product obtainable from any contiguous subarray.
WHAT IT'S REALLY ASKING
"Multiplication has a saboteur that addition does not: a negative number does not weaken you, it FLIPS you. The worst product you are carrying is one negative away from being the best product you have ever held. So what exactly do you have to carry forward?"
Multiply out every subarray
O(n^2) time, O(1) spacePick a start, extend an end, carry a running product, and track the largest you ever see.
WHERE THE WORK IS WASTED — prod(i..j+1) is just prod(i..j) times one number, yet the inner loop restarts the multiplication chain from a[i] for every new start. Two starts that overlap in 99% of their elements share 99% of their multiplications, and brute force treats them as strangers. Worse, it keeps rediscovering the same global fact — whether a run contains an even or odd number of negatives — by multiplying it out from scratch, over and over.
A negative does not weaken a product — it flips it.
Ask the Kadane question: what is the best product of a subarray ending exactly at i? The candidates are only three — a[i] alone, or a[i] times the best product ending at i-1, or a[i] times the WORST product ending at i-1. And the third one is not a curiosity, it is the whole problem. Here is why those three are enough, rigorously. Multiplying every candidate from position i-1 by the constant a[i] is a monotone map: if a[i] is positive it preserves order, if a[i] is negative it reverses it. Either way, a monotone map sends extremes to extremes — the maximum of the image is attained at either the maximum or the minimum of the pre-image, never at anything in the middle. So of all the products ending at i-1, only two can ever matter. You never need the middle ones. That is the licence to compress the entire history into two numbers. And the flip is exactly what the minimum is for. A running product of -48 is not a failure you are tolerating — it is a champion in waiting, holding its breath for the next negative number. When that negative arrives, the order reverses and your deepest liability becomes your biggest asset in one multiplication. Zero is the third character. It annihilates everything it touches: any subarray containing a zero has product zero. That is why 'start fresh at a[i]' must always be a candidate — a zero severs the array, and the run has to be allowed to restart on the other side of the cut.
Carry the best and the worst
O(n) time, O(1) space, one passHold curMax and curMin. At each element, form the three candidates — a[i], curMax * a[i], curMin * a[i] — and take the max of them for the new curMax and the min for the new curMin. Compute both from the OLD pair; overwrite curMax first and you will feed the new value into curMin's computation, which is the bug everyone writes once. Track the global best as you go.
Odd negatives: the winner is a prefix or a suffix.
There is a second, completely independent route, and it is worth knowing because it is four lines. Zeros chop the array into segments; treat each segment alone. Inside a segment, count the negatives. If the count is even, the product of the WHOLE segment is positive, and since every element has magnitude at least 1, no sub-piece can beat the whole thing — the answer for that segment is the entire segment. If the count is odd, the whole segment is negative, so you must throw away an odd number of negatives — at least one. But subarrays are contiguous: you cannot excise a negative from the middle. You can only cut from the left edge or the right edge. So the optimal subarray must be a suffix of the segment (having cut off a prefix through some negative) or a prefix of it (having cut off a suffix). It cannot be strictly interior — if it were, you could extend it outward to one of the edges and, because the discarded piece would have to be positive, extending could only make the product bigger. So every candidate you need is either a prefix product or a suffix product. Sweep left to right accumulating a running product and resetting to 1 whenever you hit a zero; sweep right to left doing the same. The answer is the largest value either sweep ever held.
Prefix sweep, suffix sweep
O(n) time, O(1) space, two passesRun a product left to right, resetting to 1 after every zero, recording the maximum. Do it again right to left. Take the best of the two. No DP, no case analysis on signs, and no way to get the min/max update order wrong.
Carry Both Extremes
YOU'LL SEE IT AGAIN WHEN
- The combining operation can reverse order — negative multipliers, sign flips, complements — so today's worst is a candidate to become tomorrow's best.
- You want the best value ending at each position, but the transition is not monotone in the accumulated value, so 'best so far' is not a sufficient state.
- There is an annihilator (a zero, an infinity, a forbidden element) that severs the array into independent segments.