Maximum Product Subarray — Why Kadane's Fails and How to Fix It [Google, Amazon, Microsoft]

Problem Statement

Given an integer array nums, find a contiguous subarray (containing at least one number) which has the largest product and return the product.

A subarray is a contiguous non-empty sequence of elements within an array.

Example 1 — All Positives:

Input:  nums = [2, 3, 4]
Output: 24
Reason: The entire array [2, 3, 4] gives 2 × 3 × 4 = 24.

Example 2 — Negatives Change Everything:

Input:  nums = [-2, 3, -4]
Output: 24
Reason: The entire array [-2, 3, -4] gives (-2) × 3 × (-4) = 24.
        NOT just [3] = 3, which a naive approach would return.

Example 3 — Zeros Act as Hard Resets:

Input:  nums = [2, 3, -2, 4]
Output: 6
Reason: [2, 3] gives 2 × 3 = 6. The -2 and 4 cannot help because
        the -2 breaks the chain and 4 alone is less than 6.

Constraints:

• 1 <= nums.length <= 2 × 10^4
• -10 <= nums[i] <= 10
• The product of any subarray fits in a 32-bit integer

• Why This Problem Matters
• Why Kadane's Algorithm Fails Directly
• The Key Insight — Track Both cur_max and cur_min
• Handling Zeros
• Visual Dry Run
• Dry Run 1: [-2, 3, -4] — Expected: 24
• Dry Run 2: [2, 3, -2, 4] — Expected: 6
• Common Mistakes
• Mistake 1 — Applying Kadane's Directly for Sums
• Mistake 2 — Not Initializing to nums[0]
• Mistake 3 — Updating cur_max Before Using the Old Value
• Mistake 4 — Forgetting the "Start Fresh" Candidate
• Solutions
• Approach 1 — Brute Force: O(n²) Time, O(1) Space
• Approach 2 — Optimal DP: O(n) Time, O(1) Space
• Complexity Analysis
• Follow-up Questions
• 1. Maximum Product Subarray with Zeros Only — Simplification
• 2. Maximum Product of Three Numbers (LC 628) — Easy
• 3. Maximum Product Subarray in a Circular Array
• 4. Maximum Sum Subarray (LC 53) Comparison — Why One Variable Suffices There
• This Pattern Solves
• Key Takeaway

Why This Problem Matters

LeetCode 152 sits at a sweet spot: it looks familiar — "find the best subarray" is something you solved in Maximum Sum Subarray — but it hides a non-obvious twist that trips nearly every candidate the first time. That twist is not just a minor implementation detail; it forces you to rethink a core assumption of Kadane's algorithm from scratch.

Where it appears: Google, Amazon, and Microsoft all use this problem. At Google, it tests whether you understand why the direct adaptation of a known algorithm fails and can reason from first principles to the fix. At Amazon, it surfaces in assessments as a pattern recognition test. At Microsoft, it often pairs with Maximum Sum Subarray (LC 53) in back-to-back rounds to see if you can articulate the difference.

The pattern it teaches: This problem is your first encounter with a broader DP pattern: "I need to track not just the optimal value but also the anti-optimal value, because the anti-optimal can flip into the optimal under certain conditions." You will see this pattern again in:

• Stock buying and selling with cooldown (LC 309)
• Minimum cost climbing stairs with negative rewards
• Any problem where the worst state today might become the best state tomorrow due to a "sign flip" operation

Why it is rated Medium and not Easy: It is not about coding complexity — the optimal solution is 8 lines of Python. The difficulty is conceptual: you have to understand why tracking a minimum is just as important as tracking a maximum when multiplication is the operation. Candidates who have only memorized Kadane's algorithm for sums will fail on this problem every single time.

Why Kadane's Algorithm Fails Directly

Let us be precise about what Kadane's algorithm does for the sum variant. In Maximum Sum Subarray, at each index you decide: do I extend the current subarray, or do I start fresh? The rule is:

cur_sum = max(num, cur_sum + num)

This works for sums because a negative number always makes the current sum worse. If cur_sum + num < num, you are better off discarding everything and starting fresh at num. The key assumption: a bad current state can only make a future state worse.

For products, this assumption collapses. A very negative product right now is not just "bad" — it is potentially the most valuable thing in the entire array. Here is why:

Negative × Negative = Positive.

The most negative product you can accumulate might instantly become the maximum product the moment you hit another negative number. You cannot afford to discard it.

Concrete example: [-2, 3, -4]

What Kadane's algorithm (adapted naively for products) would do:

Start: cur_max = -2, result = -2

Step 2, num = 3:
  max(3, -2 × 3) = max(3, -6) = 3
  cur_max = 3, result = 3

Step 3, num = -4:
  max(-4, 3 × -4) = max(-4, -12) = -4
  cur_max = -4, result = 3

Final answer: 3

But the correct answer is 24, because (-2) × 3 × (-4) = 24. The naive approach discarded the subarray at step 2 (choosing to restart at 3 rather than carrying the -6 forward) and that -6, if kept, would have yielded 24 when multiplied by -4.

The naive Kadane's adaptation is wrong because it only tracks the maximum product ending at each position. It does not know that the minimum product ending here is -6, and that -6 multiplied by -4 would give 24 — the true global maximum.

The Key Insight — Track Both cur_max and cur_min

The fix is elegant once you see it:

At every position, track both the maximum and minimum product of any subarray ending at that index.

Why do you need the minimum? Because when you encounter a negative number, it flips the sign of every product you multiply it with. The current maximum becomes the current minimum, and the current minimum becomes the current maximum. The only way to capture this flip correctly is to maintain both values.

Here is the insight stated precisely:

If the current number is negative, cur_min × num (a negative times a negative) might be the largest thing you can build. If the current number is positive, cur_max × num is the largest thing. Either way, you need both cur_max and cur_min to make the right decision.

At each step, three candidates compete for the new cur_max:

1. num — start a completely new subarray at this position
2. cur_max × num — extend the current best product
3. cur_min × num — extend the current worst product (only wins when num < 0)

Similarly, three candidates compete for the new cur_min:

1. num — start fresh (this wins when num is the most negative so far)
2. cur_max × num — extending a large positive product by a negative number produces a very negative result
3. cur_min × num — extending a very negative product by a positive number stays very negative

The algorithm:

cur_max = cur_min = result = nums[0]

for each num in nums[1:]:
    # All three candidates — compute BEFORE updating anything
    candidates = (num, cur_max * num, cur_min * num)
    cur_max = max(candidates)
    cur_min = min(candidates)
    result  = max(result, cur_max)

return result

Why we compute all three candidates simultaneously: This is subtle but critical. When you update cur_max first and then compute cur_min, the cur_min formula uses the already-updated cur_max, producing a wrong result. Always compute both new values from the old cur_max and old cur_min.

An alternative formulation that makes the swap semantics explicit:

for each num in nums[1:]:
    if num < 0:
        cur_max, cur_min = cur_min, cur_max   # swap — negative flips the sign
    cur_max = max(num, cur_max * num)
    cur_min = min(num, cur_min * num)
    result  = max(result, cur_max)

Both formulations are equivalent. The swap version is easier to reason about when teaching the concept. The three-candidate version is more concise in code.

Handling Zeros

Zeros are the second important case. When num = 0:

• cur_max × 0 = 0
• cur_min × 0 = 0
• num = 0

All three candidates are 0, so both cur_max and cur_min become 0. This is the correct behavior: any subarray that includes a zero has product zero, so after a zero you must start fresh. The algorithm handles this automatically — you do not need special-case logic.

The only nuance: if all numbers in the array are negative, or if the only non-zero numbers are negative, you still want to consider single-element subarrays (just num itself). The num candidate in the three-candidate formula handles this: starting fresh is always an option.

Example: [-2, 0, -1]

Initialize: cur_max = -2, cur_min = -2, result = -2

num = 0:
  candidates = (0, -2×0, -2×0) = (0, 0, 0)
  cur_max = 0, cur_min = 0
  result = max(-2, 0) = 0

num = -1:
  candidates = (-1, 0×-1, 0×-1) = (-1, 0, 0)
  cur_max = 0, cur_min = -1
  result = max(0, 0) = 0

Answer: 0

Correct — no non-zero subarray avoids a zero penalty, so 0 is the best we can do.

Visual Dry Run

Let us trace through two key examples showing every variable at every step.

Dry Run 1: [-2, 3, -4] — Expected: 24

Step 2 walkthrough: With num = -4:

• Start fresh: -4
• Extend cur_max: 3 × -4 = -12 (positive becomes large negative — bad)
• Extend cur_min: -6 × -4 = 24 (negative × negative = large positive — best!)

This is the entire magic of the problem. The -6 we accumulated at step 1 (the minimum!) is exactly what we needed to hit 24 at step 2. If we had discarded it (as Kadane's does), we would have gotten 3.

Dry Run 2: [2, 3, -2, 4] — Expected: 6

Step 2 walkthrough: The -2 collapses our cur_max from 6 to -2. The minimum shoots down to -12. Neither helps us improve the global result of 6. Starting fresh at 4 in step 3 only gives 4, which is still less than 6. So [2, 3] is the winning subarray.

This shows that zeros and negatives that do not lead to a "double negative" redemption simply degrade the running products, and the global result captures the best we have seen before the damage occurred.

Common Mistakes

Mistake 1 — Applying Kadane's Directly for Sums

The most common error: candidates substitute * for + in Kadane's formula and call it done:

# WRONG for products
cur_max = max(num, cur_max * num)
result = max(result, cur_max)

This misses the flip. When num is negative, cur_max * num might be smaller than cur_min * num, and you never compute cur_min, so you lose the "negative redeems negative" case entirely. The array [-2, 3, -4] returns 3 instead of 24.

Mistake 2 — Not Initializing to nums[0]

A common bug:

cur_max = cur_min = result = 0   # WRONG

If all numbers are negative, the correct answer is the single largest (least negative) element. Initializing to 0 and then never checking single-element subarrays causes the algorithm to return 0 when the real answer is, say, -1 (for [-3, -1, -2]). Always initialize all three variables to nums[0] and start the loop from index 1.

Mistake 3 — Updating cur_max Before Using the Old Value

# WRONG — uses new cur_max to compute cur_min
cur_max = max(num, cur_max * num, cur_min * num)
cur_min = min(num, cur_max * num, cur_min * num)  # cur_max is already updated!

You must save the old cur_max before overwriting it, or compute both new values simultaneously from the old values. In the three-candidate approach, collect all candidates first, then assign. In the swap approach, swap first, then update independently.

Mistake 4 — Forgetting the "Start Fresh" Candidate

# WRONG — missing the restart option
cur_max = max(cur_max * num, cur_min * num)

When all preceding products have been devastated by zeros or an unfortunate sign pattern, starting fresh at just num may be the best option. The num candidate (no multiplication) represents breaking away from the current subarray and starting a new one. Without it, you can end up carrying a chain of zeros or large negatives indefinitely.

Solutions

Approach 1 — Brute Force: O(n²) Time, O(1) Space

Try every possible subarray and track the maximum product. Correct but too slow for large inputs — this exists to build confidence before the optimal solution.

Python:

from typing import List

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        n = len(nums)
        result = nums[0]  # single element is the minimum valid subarray

        for i in range(n):
            product = 1
            for j in range(i, n):
                product *= nums[j]           # extend subarray from i to j
                result = max(result, product)  # track global maximum

        return result

JavaScript:

/**
 * Brute force — try every subarray, O(n²) time
 * @param {number[]} nums
 * @return {number}
 */
function maxProduct(nums) {
    let result = nums[0]; // single element baseline

    for (let i = 0; i < nums.length; i++) {
        let product = 1;
        for (let j = i; j < nums.length; j++) {
            product *= nums[j];              // extend subarray from i to j
            result = Math.max(result, product); // track global maximum
        }
    }

    return result;
}

Complexity: O(n²) time, O(1) space. Fails for n = 20,000 but useful for verifying against the optimal solution.

Approach 2 — Optimal DP: O(n) Time, O(1) Space

Track both cur_max and cur_min at each step. Single pass. This is the answer to give in any interview.

Python:

from typing import List

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        # Initialize all three tracking variables to the first element.
        # This handles single-element arrays and ensures negatives are considered.
        cur_max = cur_min = result = nums[0]

        for num in nums[1:]:
            # Compute all three candidates BEFORE updating anything.
            # candidate 1: num alone — start a new subarray here
            # candidate 2: cur_max * num — extend the best product
            # candidate 3: cur_min * num — extend the worst product (wins when num < 0)
            candidates = (num, cur_max * num, cur_min * num)

            # The new maximum might come from any of the three candidates.
            # Crucially, cur_min * num can win when num is negative.
            cur_max = max(candidates)
            cur_min = min(candidates)

            # Update the global best seen so far
            result = max(result, cur_max)

        return result

JavaScript:

/**
 * Optimal DP — O(n) time, O(1) space
 * Track both max and min products to handle negative × negative = positive.
 * @param {number[]} nums
 * @return {number}
 */
function maxProduct(nums) {
    // Initialize to first element — handles single-element input
    let curMax = nums[0];
    let curMin = nums[0];
    let result = nums[0];

    for (let i = 1; i < nums.length; i++) {
        const num = nums[i];

        // Save curMax before overwriting — we need the old value for curMin
        const prevMax = curMax;

        // New curMax: best of (start fresh, extend max, extend min)
        // When num < 0, curMin * num (negative * negative) often wins
        curMax = Math.max(num, prevMax * num, curMin * num);

        // New curMin: worst of (start fresh, extend old max, extend min)
        // When num > 0, curMin * num stays most negative
        // When num < 0, prevMax * num becomes most negative
        curMin = Math.min(num, prevMax * num, curMin * num);

        // Track the global maximum across all positions
        result = Math.max(result, curMax);
    }

    return result;
}

Note on JavaScript: We save prevMax before the update because JavaScript executes assignments sequentially. If we updated curMax first, the curMin formula would use the already-updated value, producing wrong results. The Python solution avoids this by computing all candidates at once before any assignment.

Complexity Analysis

Why O(n) time: A single pass through the array, with O(1) work per element (three multiplications, two max/min calls, one comparison). No nested loops, no sorting, no auxiliary data structures.

Why O(1) space: We maintain exactly three variables — cur_max, cur_min, and result — regardless of the input size. No arrays, no hash maps, no recursion stack.

Comparison with Maximum Sum Subarray (LC 53): Both are O(n) time and O(1) space. The sum version tracks one variable (cur_sum). The product version tracks two (cur_max and cur_min). The extra variable is the entire algorithmic difference, and it comes directly from the "negative × negative" property of multiplication.

Follow-up Questions

1. Maximum Product Subarray with Zeros Only — Simplification

If the array is guaranteed to contain only zeros and positive integers (no negatives), you do not need cur_min. A single Kadane's-style pass with just cur_max = max(num, cur_max * num) works correctly because zeros reset to zero and positives only grow the product. The "track minimum" complexity disappears entirely.

This is a good interview sanity check: "What if all values were non-negative?" Shows you understand exactly which part of the problem motivates each part of the solution.

2. Maximum Product of Three Numbers (LC 628) — Easy

Given an integer array, find three numbers whose product is maximum and return the maximum product. Note: the numbers do not have to be contiguous.

The key insight here is that you only have two candidates for the maximum product of three:

• The three largest numbers: nums[-1] × nums[-2] × nums[-3]
• The two smallest (most negative) numbers times the largest: nums[0] × nums[1] × nums[-1]

Sort the array and compare these two. O(n log n) or O(n) with a linear scan tracking only the top 3 and bottom 2. This problem reuses the "negative × negative" insight from LC 152 but applies it in a much simpler non-contiguous context.

3. Maximum Product Subarray in a Circular Array

What if the array wraps around — the subarray can start at index 5 and end at index 2, going through the end and back to the beginning?

The standard approach: run LC 152 twice. First on the original array (normal subarrays). Then consider the "complement" subarray — the minimum product subarray wrapped around contributes to the maximum circular product. The circular maximum = total product / minimum product subarray. Handle all-negatives and zeros as edge cases.

This is an excellent follow-up that tests whether you can compose known solutions rather than inventing from scratch.

4. Maximum Sum Subarray (LC 53) Comparison — Why One Variable Suffices There

In the sum variant, a negative number can only make a sum smaller — it can never make it larger. So once cur_sum + num < num (i.e., cur_sum < 0), there is no reason to keep cur_sum: it is actively hurting you and it cannot magically become helpful later the way a large negative product can.

With products, a large negative product right now is one negative-number encounter away from being the largest positive product. The asymmetry between sum and product is precisely why you need cur_min in LC 152 but not in LC 53.

This Pattern Solves

The "track both the maximum and the anti-maximum" DP pattern appears whenever an operation can flip signs or reverse the order of values:

The meta-lesson: any time your DP update involves a non-monotone operation (one that can reverse the ordering of values), ask yourself whether the current worst state could become a future best state. If yes, track both.

Key Takeaway

Maximum Product Subarray looks like a simple restatement of Maximum Sum Subarray, but the multiplication operator breaks the core assumption of Kadane's algorithm: that a bad current state cannot become a good future state. Because negative times negative is positive, the current minimum product is always one negative-number away from becoming the maximum product. The fix — tracking both cur_max and cur_min at every step and computing both from the same old values before either is updated — is the entire insight of this problem.

If you remember only one thing: zeros reset, negatives flip, and you always need both the best and the worst product ending at the current position. That sentence contains the entire algorithm.