Algorithm

Maximum Product Subarray

Arrays & Strings Pattern

Maximum Product Subarray

Given an integer array nums, find a contiguous non-empty subarray that has the largest product, and return the product.

CONSTRAINTS
  • 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
EXAMPLE 1
Input: nums = [2,3,-2,4]
Output: 6
[2, 3] gives 6. Extending across the -2 flips the product negative, and 4 alone cannot beat 6.
EXAMPLE 2
Input: nums = [-2,0,-1]
Output: 0
Every window either contains the zero (product 0) or is stuck negative. The single-element window [0] achieves the best possible: 0.
EXAMPLE 3
Input: nums = [-2,3,-4]
Output: 24
The two negatives cancel: (-2) × 3 × (-4) = 24. Taking the whole array wins.
EXAMPLE 4
Input: nums = [-2]
Output: -2
Only one non-empty subarray exists. The answer can be negative when nothing better is available.
Does 'subarray' mean contiguous here too?
Yes — an unbroken slice with at least one element, same definition as in Maximum Subarray.
Can the answer be negative?
Yes. The subarray must be non-empty, so nums = [-2] returns -2. (Though if the array contains any zero, the answer is never below 0 — the window holding just that zero already achieves 0.)
Should I worry about the product overflowing?
Excellent question to ask — products explode far faster than sums. Here the constraints promise every subarray product fits in a 32-bit integer, so no special handling is needed. Without that promise you would raise it: a wider integer type, or discussing bounds with the interviewer.
What happens at a zero?
Every window containing it multiplies to 0, so both trackers honestly become 0 there (and 0 is recorded as a candidate answer). The next step's max(num, ...) choice then starts a fresh streak — zeros split the array into independent segments with no extra code.

Same setting as Maximum Subarray — choose a contiguous, non-empty slice — but now we multiply its elements and want the largest product. If Kadane's reasoning carried over unchanged, this page would be one line long. It does not, and pinpointing exactly where it breaks is the entire lesson. Multiplication has two behaviors that addition lacks: a negative number flips the sign, turning the largest value into the smallest and vice versa, and a zero annihilates, collapsing any window that contains it to 0.

The honest brute force, again

As before, a subarray is a (start, end) choice, sliding the end extends the running product by one multiplication, and there are roughly N²/2 windows — so checking them all costs O(N²):

python
res = nums[0]
for i in range(len(nums)):
    current_prod = 1
    for j in range(i, len(nums)):
        current_prod *= nums[j]      # extend the running product by one number
        res = max(res, current_prod)
return res
Where Kadane's logic breaks

Try to reuse yesterday's reframe directly: "track the best product ending at each position — either the element alone, or the previous best extended." Watch it fail on [-2, 3, -4]. The best product ending at the 3 is 3 (because -2 × 3 = -6 is worse). Carrying only that, at -4 we would choose max(-4, 3 × -4 = -12) = -4, and answer 3. The true answer is (-2) × 3 × (-4) = 24. What did we throw away? The worst product ending at the 3, which was -6. One step later, multiplying that miserable -6 by -4 produces 24 — the sign flip turned the worst product into the best. In sums, a deeply negative running total is irredeemable dead weight; Kadane's is right to dump it. In products, it is a coiled spring — one more negative number away from being enormous. Remembering only the best is simply not enough information.

The fix: carry the best AND the worst

So ask carefully: with x = nums[i], what can the best product ending at position i possibly be? Any subarray ending at i is x times some subarray ending at i - 1, or x alone. Multiplying by a positive x keeps the ranking of the previous products — the biggest stays biggest. Multiplying by a negative x reverses the ranking — the smallest previous product becomes the biggest. And x = 0 flattens everything to 0. So only three candidates can ever win: x alone, x × (best ending at i-1), and x × (worst ending at i-1). The identical three candidates (taking the minimum) cover the worst.

Key Insighttwo running values — the maximum AND the minimum product ending here — carry all the information the future could ever need. The most negative product is not garbage to be dumped; it is a candidate future maximum, and it must be kept alive.
python
max_p = min_p = result = nums[0]
for i in range(1, len(nums)):
    num = nums[i]
    if num < 0:
        max_p, min_p = min_p, max_p   # a negative flips the ranking, so the roles swap
    max_p = max(num, num * max_p)     # best product ending here
    min_p = min(num, num * min_p)     # worst product ending here
    result = max(result, max_p)
return result

The swap line is the three-candidate rule in compressed form: when num is negative, it is the old minimum that can produce the new maximum, so the two trade places before the usual "extend or start fresh" choice runs.

What about zeros?

Zeros need no special code, and seeing why is instructive. When num is 0, both updates collapse to max(0, 0) = 0 — which is the honest truth: every subarray ending at the zero has product 0. result records that 0, and that matters: in [-2, 0, -1] no positive product exists anywhere, and the correct answer is 0, achieved by the one-element window [0]. On the next element, the max(num, ...) choice naturally starts a fresh streak. So a zero quietly acts as a wall between product streaks — with no extra code at all.

Worked Example:nums = [2, 3, -2, 4]
- Start: max = min = result = 2.
- num = 3 (positive): max = max(3, 3 × 2) = 6; min = min(3, 3 × 2) = 3. Result = 6.
- num = -2 (negative — swap first: max = 3, min = 6): max = max(-2, -2 × 3) = -2; min = min(-2, -2 × 6) = -12. Result stays 6.
- num = 4 (positive): max = max(4, 4 × -2) = 4; min = min(4, 4 × -12) = -48. Result stays 6.
- Answer: 6, from [2, 3]. Note the machine is still carrying min = -48 — useless here, but a single further negative number would have flipped it into a huge positive.
Worked Example:nums = [-2, 3, -4] — the payoff
- Start: max = min = result = -2.
- num = 3 (positive): max = max(3, 3 × -2) = 3; min = min(3, -6) = -6. Result = 3.
- num = -4 (negative — swap first: max = -6, min = 3): max = max(-4, -4 × -6) = 24; min = min(-4, -4 × 3) = -12. Result = 24.
- Answer: 24. The -6 we refused to throw away became the answer one step later.
The takeaway

One pass, O(N) time, O(1) extra space — the same cost as Kadane's, for the price of one extra tracked value. The lesson here is subtle and very transferable. The "best ending here" reframe survived the change of operation; what changed is what must be remembered. Addition never reorders past results, so one running value suffices. Multiplication can invert the entire ranking, so you must keep every past value that could still become optimal — here, exactly the two extremes. Whenever you adapt a known technique to a new setting, re-ask the question: "what information does the future actually need from the past?" Getting that answer wrong — not the coding — is where this problem defeats people.

Interactive Strategy Visualization

The Sign Flipper

Record Max: 2
2
3
-2
4
-2
Positive High
2
Negative Low
2
Starting with 2. Max and Min both begin here.
INSIGHT

Negatives are risky but valuable. They can turn the worst min into the best max instantly.

EFFICIENCY

We find the record in one single pass by keeping track of both extremes at every step.

O(N²) Brute Force
→
O(N) Max & Min Tracking