Maximum Product Subarray

Track max AND min ending here

time O(n)space O(1)

Kadane's sum logic fails here because multiplication is sign-sensitive: a huge negative running product can become a huge positive one the moment another negative arrives — but only if we REMEMBER it. So each index keeps two runners: curMax and curMin, the best AND worst products of subarrays ending right there. A negative element swaps their roles before they absorb it.

Details

Animated on: Find the contiguous subarray of [2,3,-2,4,-1,3] with the largest PRODUCT.

Problem:Maximum Product SubarrayMedium

Track max AND min ending here

step 1 / 9

[0]

[1]

-2

[2]

[3]

-1

[4]

[5]

Seed both runners with the first cell: curMax = curMin = best = 2. curMax is the best product ending here, curMin the WORST — keep it, negatives can resurrect it.

i=0· arr[0] = 2

Pseudocode

1FUNCTION maxProduct(nums):
2  set curMax, curMin and best all to nums[0]
3  FOR each x in nums from index 1 onward:
4    IF x < 0: swap curMax and curMin
5    curMax = the larger of x and (curMax * x)
6    curMin = the smaller of x and (curMin * x)
7    best = the larger of best and curMax
8  RETURN best

← / → step · space play · Home restart

Every step in words

Show all 9 steps

Seed both runners with the first cell: curMax = curMin = best = 2. curMax is the best product ending here, curMin the WORST — keep it, negatives can resurrect it.
x = 3: extend beats restart (2·3 = 6 > 3), so curMax = 6 over run [2,3]; curMin rises to 3. best = 6.
x = −2 is negative → swap curMax ↔ curMin FIRST (now 3 and 6). Why: multiplying by a negative flips big↔small, so yesterday's minimum becomes tomorrow's maximum candidate.
After the swap both runners multiply by −2: curMax = max(−2, 3·−2 = −6) → −2 alone; curMin = min(−2, 6·−2 = −12) → −12, which is run [2,3,−2]. The old champion 6 just became the floor. best holds at 6.
x = 4 (positive): curMax = max(4, −2·4 = −8) → fresh start at 4. But curMin plunges to min(4, −12·4) = −48 — run [2,3,−2,4]. Looks useless… bank it anyway.
x = −1, negative again → swap: curMax becomes −48, curMin becomes 4. This swap is the whole trick — the buried −48 is about to compete.
THE payoff: curMax = max(−1, −48 × −1) = +48 — a brand-new best! Tracking the minimum MANUFACTURED this maximum; Kadane-sum thinking would have thrown −48 away. curMin = −4; best jumps to 48.
x = 3 rides the hot streak: curMax = max(3, 48·3) = 144 over [2,3,−2,4,−1,3]; curMin = min(3, −4·3) = −12. best = 144.
Answer: 144 — the ENTIRE array's product: 2·3·(−2)·4·(−1)·3 = 144. It only surfaced because curMin carried −12 → −48 through the lean patches until a second negative flipped it rich.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Maximum Product Subarray in the editor All Arrays problems Back to roadmap