Maximum Product Subarray

1. Problem & Core Objective

Find the contiguous subarray with the largest product and return that product.

nums = [2,3,-2,4]    →  6      [2,3]
nums = [-2,0,-1]     →  0      [0]
nums = [-2,3,-4]     →  24     the whole array

Constraints: 1 <= nums.length <= 2 × 10^4 · -10 <= nums[i] <= 10 · the answer fits in a 32-bit integer

What's actually being tested: that a minimum can become a maximum. Multiplying by a negative flips the sign, so the smallest product so far is a candidate for the largest after the next element. You must track both extremes — which is the difference from Maximum Subarray (sum), where only the maximum matters.

2. First-Principles Thought Process

Why the sum version's approach fails

For sums, Kadane's works: best ending here = max(nums[i], best + nums[i]). A running maximum is all you need, because adding never inverts an ordering.

Multiplication does invert. −8 × −3 = 24 — the most negative running product became the largest.

So a single "max ending here" is insufficient: the value that produces the next maximum may be the current minimum.

Track both extremes

maxEnding[i] = max(nums[i], maxEnding[i−1] × nums[i], minEnding[i−1] × nums[i])
minEnding[i] = min(nums[i], maxEnding[i−1] × nums[i], minEnding[i−1] × nums[i])

Three candidates each: start fresh at nums[i], extend the running max, or extend the running min.

Why nums[i] alone is a candidate

Because a subarray may start here. That's what handles zeros: after a 0, both running products are 0, and the next element must be free to begin a new subarray rather than being multiplied into nothing.

Without that term, [-2, 0, -1] would never recover from the zero.

The update-order trap

maxEnding and minEnding must both be computed from the previous values. Updating max first and then using it to compute min reads the new value and produces nonsense.

int temp = maxEnding;                                       // save the old max
maxEnding = max(n, maxEnding * n, minEnding * n);
minEnding = min(n, temp * n, minEnding * n);                // use the SAVED one

This is the same snapshot discipline as Bellman-Ford's clone and BFS's level size — read the previous generation, not the partially-updated one.

3. Solution Paths

Approach 1 — Every subarray (brute force)

public int maxProduct(int[] nums) {
    int best = nums[0];
    for (int i = 0; i < nums.length; i++) {
        int product = 1;
        for (int j = i; j < nums.length; j++) {
            product *= nums[j];                     // extend, don't recompute
            best = Math.max(best, product);
        }
    }
    return best;
}

• Time O(n²) · Space O(1)

Counter-questions on this approach

⭐ "Is O(n²) fast enough at n = 2 × 10^4?"

4 × 10^8 multiplications — too slow in Java, probably by several seconds. The linear version is 2 × 10^4.

⭐ "It at least extends the product rather than recomputing. Why is that worth noting?"

Because the naive nesting would recompute nums[i..j] from scratch for each j, making it O(n³). Carrying product across the inner loop is a real improvement and gets it to O(n²).

The linear solution takes the same idea one step further: carry state across the outer loop too, which requires knowing what state suffices — and that's the min/max insight.

"Could the intermediate product overflow?"

Yes. Values up to 10 over 20,000 elements gives 10^20000, which overflows long before the end. The problem guarantees the answer fits in 32 bits, but intermediate products need not — a long run of 2s would overflow.

In practice a 0 or a small value usually intervenes, but the brute force has no protection. The linear version is safer only because it resets at zeros and the problem's guarantee covers the tracked extremes.

Approach 2 — Track max and min ending here (optimal)

public int maxProduct(int[] nums) {
    int maxEnding = nums[0], minEnding = nums[0], best = nums[0];

    for (int i = 1; i < nums.length; i++) {
        int n = nums[i];
        int prevMax = maxEnding;                    // snapshot before overwriting

        maxEnding = Math.max(n, Math.max(prevMax * n, minEnding * n));
        minEnding = Math.min(n, Math.min(prevMax * n, minEnding * n));

        best = Math.max(best, maxEnding);
    }
    return best;
}

Trace — nums = [-2, 3, -4]:

Answer 24 ✓ — and note it came from minEnding × n, the tracked minimum.

• Time O(n) · Space O(1)

Counter-questions on this approach

⭐ "Why track the minimum at all?"

Because multiplying by a negative flips the ordering. The most negative running product becomes the largest when multiplied by a negative number.

The trace shows it exactly: at i = 2, the answer 24 comes from minEnding × n = −6 × −4. Without tracking the minimum, the best available would have been 3 × −4 = −12, and the answer would be 3.

That's the whole difference from the sum version — addition never inverts an ordering, so Kadane's needs only one running value.

⭐ "Why is nums[i] itself one of the three candidates?"

Because a subarray may start at i. That's what lets the algorithm recover from a zero: after a 0 both running products are 0, and nums[i] alone lets a fresh subarray begin.

On [-2, 0, -1], at i = 2 the candidates are −1, 0 × −1 = 0, and 0 × −1 = 0. Taking max gives 0, which is the correct answer. Without the nums[i] term the running values would be stuck and the minEnding needed for a later negative flip would be wrong.

⭐ "Explain the prevMax snapshot. What breaks without it?"

Both updates must read the previous generation. If maxEnding is overwritten first, the minEnding line uses the new value instead of the old one.

I tested both. On [-2, 3, -4] the corruption is visible but silent — minEnding ends at −96 instead of −12, while the returned answer happens to still be 24.

On [-1, -2, -3] it produces a wrong answer: 12 instead of 6. And 12 isn't even achievable — the subarray products are −1, 2, −6, −2, 6, −3, so 6 is the maximum. The bug invents a value.

That's worth knowing: the missing snapshot corrupts the state immediately but only sometimes surfaces in the result, which is exactly the kind of bug that survives casual testing.

It's the same read-the-previous-generation discipline as Bellman-Ford's array clone.

"Why is best seeded with nums[0] rather than 0 or Integer.MIN_VALUE?"

Because the array may be entirely negative, in which case the answer is negative and 0 would be wrong. [-2] should return −2, not 0.

And Integer.MIN_VALUE works but is unnecessary — nums[0] is a real achievable value, which makes the seeding self-evidently correct.

"Does this handle zeros without a special case?"

Yes. At a zero, all three candidates are 0 (n, prevMax × 0, minEnding × 0), so both running values become 0 — and the next element can start fresh via the nums[i] term.

No explicit reset is needed, which is worth checking rather than adding a defensive branch.

"Could the running products overflow?"

The problem guarantees the answer fits in 32 bits. The tracked extremes are products of contiguous subarrays, and any that overflows would exceed the answer bound — so under the guarantee they stay in range.

That's a guarantee about the test data rather than the input space, though. With values up to 10 and length 2 × 10^4, an all-2s array would overflow enormously. Worth naming.

Approach 3 — Prefix/suffix products

public int maxProduct(int[] nums) {
    int n = nums.length, best = nums[0];
    int prefix = 0, suffix = 0;

    for (int i = 0; i < n; i++) {
        prefix = (prefix == 0 ? 1 : prefix) * nums[i];
        suffix = (suffix == 0 ? 1 : suffix) * nums[n - 1 - i];
        best = Math.max(best, Math.max(prefix, suffix));
    }
    return best;
}

• Time O(n) · Space O(1)

Counter-questions on this approach

⭐ "Why does scanning both directions work?"

The maximum product subarray either contains an even number of negatives, or it's bounded by a zero. If the array has an even count of negatives overall, the whole array works. Otherwise the optimum runs from one end up to just before some negative — and scanning from both ends catches whichever side that is.

The == 0 ? 1 reset handles zeros by restarting the running product.

"Which would you write?"

The max/min version. This one is shorter but its correctness argument is much less obvious — "scan both ways" requires the parity reasoning above, whereas the min/max version follows directly from the recurrence.

I'd mention it as a neat alternative, not as the primary answer.

Comparison

4. Why the Optimal Wins

The quadratic version examines every subarray. The linear version carries just enough state to extend the answer one element at a time — and the insight is what state suffices.

For sums it's one value. For products it's two, because multiplying by a negative flips the ordering and the running minimum is a candidate for the next maximum.

The framing worth keeping:

A minimum can become a maximum. Multiplying by a negative inverts the ordering, so track both extremes — and include nums[i] alone as a candidate so a subarray can start fresh after a zero.

And the implementation discipline: snapshot the old max before overwriting it, or the min update reads the wrong generation.

5. Java Prerequisites

Both extremes, three candidates each

int prevMax = maxEnding;                                  // snapshot FIRST
maxEnding = Math.max(n, Math.max(prevMax * n, minEnding * n));
minEnding = Math.min(n, Math.min(prevMax * n, minEnding * n));

Nested Math.max — it takes two arguments, so three candidates need nesting.

Seed from nums[0], not 0 — the answer can be negative.

Zeros need no special case — all three candidates become 0, and nums[i] lets the next element start fresh.

6. Interview Communication Guide

Clarifying questions: Contiguous subarray (yes — subsequence would be different)? Can it be empty (no — at least one element)? Can values be 0 or negative (yes — both matter)? Does the answer fit in int (guaranteed, though intermediates could overflow in principle)?

The pitch

"Kadane's algorithm works for sums because addition never inverts an ordering — a running maximum is all the state you need.

Multiplication does invert. Multiplying by a negative flips the sign, so the most negative running product can become the largest. −6 × −4 = 24.

So I track both extremes ending at each index: the maximum and the minimum. Each has three candidates — start fresh at nums[i], extend the running max, or extend the running min.

The nums[i] term is what lets a subarray start here, which is how zeros are handled without a special case. After a zero both running products are 0, and the next element can begin a new subarray rather than being multiplied into nothing.

One implementation detail that's easy to get wrong: both updates must read the previous values. If I overwrite maxEnding first, the minEnding line uses the new one. On [-1, -2, -3] that returns 12 instead of 6 — a value no subarray actually achieves. So I snapshot the old max before assigning.

Same read-the-previous-generation discipline as Bellman-Ford's array clone.

I seed everything from nums[0] rather than 0, because an all-negative array has a negative answer and 0 would be wrong.

O(n) time, O(1) space, versus O(n²) for checking every subarray — which would be 4 × 10^8 at these limits."

Edge cases to volunteer:

Name [-2,3,-4]. The answer 24 comes from the tracked minimum (−6 × −4), so a solution tracking only the maximum returns 3. It's the case the whole approach exists for.

7. Follow-Up Questions — Modified Constraints

⭐ "Return the subarray itself, not just the product."

Track the start index alongside each running extreme — reset it when nums[i] alone wins. Trickier than the sum version, because the max and min have different start indices that must be carried independently.

⭐ "What about the maximum SUM subarray?"

Maximum Subarray — Kadane's, with one running value. The contrast is the point: addition preserves ordering, so one extreme suffices; multiplication doesn't, so you need two.

"What if the answer could overflow int?"

Use long, or track log|nums[i]| sums plus a negative-count parity — which converts products into sums and sidesteps overflow entirely, at the cost of floating-point precision.

"Find the maximum product of a subarray of exactly length k."

A sliding window, but division by the departing element fails when it's zero. Instead maintain the window product with a zero counter, or use prefix products with the same zero care. Genuinely fiddlier than the fixed-window sum.

"What if the array were circular?"

Same case-split idea as House Robber II, but harder: for sums you'd take max(normal, total − minSubarray), and for products there's no such complement identity. You'd likely double the array and use a length-bounded window.

"What if n were 10^6?"

The linear version scales directly. Overflow becomes the real constraint long before time does — at that length even modest values produce astronomically large products.