Maximum Product Subarray — Tracking Both Min and Max for Sign Flips

Problem Statement#

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

Constraints:

• 1 <= nums.length <= 2 * 10^4
• -10 <= nums[i] <= 10
• The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.

Example 1:

Input:  nums = [2, 3, -2, 4]
Output: 6
Explanation: Subarray [2, 3] has the largest product 6.
             Including -2 or 4 does not help.

Example 2:

Input:  nums = [-2, 0, -1]
Output: 0
Explanation: The zero splits the array. No subarray with positive product exists.
             Best single element: 0.

Example 3:

Input:  nums = [-2, 3, -4]
Output: 24
Explanation: Subarray [-2, 3, -4] has product (-2)*3*(-4) = 24.
             Two negatives multiply to a positive.

Why This Problem Matters#

Maximum Product Subarray (LeetCode 152) is the natural "harder sibling" of Maximum Subarray (LC 53). It is asked at Amazon, Google, and LinkedIn as a follow-up to test whether candidates can adapt Kadane's Algorithm when the operation changes from sum to product. The key complication: a large negative product today might become the largest positive product tomorrow if the next element is also negative. This "sign flip" property breaks the straightforward extend-or-restart reasoning from Kadane's.

The dual-tracking technique — maintaining both a running maximum and a running minimum — is a valuable pattern that surfaces in other product-range problems and in certain financial modeling scenarios where direction reversals matter.

The Core Insight#

The fundamental challenge with products (versus sums) is that negativity inverts the relative order of max and min. When you multiply a very large negative number by another negative, it becomes very positive. So the minimum product at position i-1 might become the maximum product after multiplying by nums[i] if nums[i] is negative.

Define:

• max_here = maximum product of any subarray ending at index i
• min_here = minimum product of any subarray ending at index i

Transitions:

candidates = [nums[i], max_here * nums[i], min_here * nums[i]]
new_max_here = max(candidates)
new_min_here = min(candidates)

The three candidates represent: start fresh at nums[i], extend the previous max subarray, or extend the previous min subarray (which may flip sign). The global answer is max(new_max_here) over all positions.

Why track the minimum? Because min_here * nums[i] can become the new maximum when nums[i] is negative.

Why start fresh? Because multiplying by zero or certain elements resets the subarray. Starting fresh avoids negative contamination from far back.

Building the DP Solution#

Step 1 — Brute Force (O(n^2))#

# Python — brute force, O(n^2) — illustrative only
def maxProduct(nums):
    n = len(nums)
    best = float('-inf')
    for i in range(n):
        product = 1
        for j in range(i, n):
            product *= nums[j]
            best = max(best, product)
    return best

// JavaScript — brute force, O(n^2)
function maxProduct(nums) {
    let best = -Infinity;
    for (let i = 0; i < nums.length; i++) {
        let product = 1;
        for (let j = i; j < nums.length; j++) {
            product *= nums[j];
            best = Math.max(best, product);
        }
    }
    return best;
}

Step 2 — Top-Down Memoization (O(n) time, O(n) space)#

Because we need to track both max and min, memoization stores pairs (max_product, min_product) ending at each index:

# Python — top-down memoization storing (max, min) pairs
from functools import lru_cache
 
class Solution:
    def maxProduct(self, nums: list[int]) -> int:
        n = len(nums)
 
        @lru_cache(maxsize=None)
        def dp(i: int) -> tuple:
            """Returns (max_product_ending_here, min_product_ending_here)"""
            if i == 0:
                return (nums[0], nums[0])
            prev_max, prev_min = dp(i - 1)
            candidates_max = [nums[i], prev_max * nums[i], prev_min * nums[i]]
            candidates_min = [nums[i], prev_max * nums[i], prev_min * nums[i]]
            return (max(candidates_max), min(candidates_min))
 
        best = float('-inf')
        for i in range(n):
            mx, _ = dp(i)
            best = max(best, mx)
        return best

// JavaScript — top-down memoization
var maxProduct = function(nums) {
    const n = nums.length;
    const memo = new Map();
 
    function dp(i) {
        if (i === 0) return [nums[0], nums[0]];
        if (memo.has(i)) return memo.get(i);
        const [prevMax, prevMin] = dp(i - 1);
        const a = nums[i], b = prevMax * nums[i], c = prevMin * nums[i];
        const result = [Math.max(a, b, c), Math.min(a, b, c)];
        memo.set(i, result);
        return result;
    }
 
    let best = -Infinity;
    for (let i = 0; i < n; i++) {
        best = Math.max(best, dp(i)[0]);
    }
    return best;
};

Step 3 — Bottom-Up Tabulation (O(n) time, O(n) space)#

# Python — bottom-up tabulation
class Solution:
    def maxProduct(self, nums: list[int]) -> int:
        n = len(nums)
        max_dp = [0] * n
        min_dp = [0] * n
        max_dp[0] = min_dp[0] = nums[0]
        best = nums[0]
 
        for i in range(1, n):
            candidates = [nums[i], max_dp[i-1] * nums[i], min_dp[i-1] * nums[i]]
            max_dp[i] = max(candidates)
            min_dp[i] = min(candidates)
            best = max(best, max_dp[i])
 
        return best

// JavaScript — bottom-up tabulation
var maxProduct = function(nums) {
    const n = nums.length;
    const maxDp = new Array(n).fill(0);
    const minDp = new Array(n).fill(0);
    maxDp[0] = minDp[0] = nums[0];
    let best = nums[0];
 
    for (let i = 1; i < n; i++) {
        const a = nums[i], b = maxDp[i-1] * nums[i], c = minDp[i-1] * nums[i];
        maxDp[i] = Math.max(a, b, c);
        minDp[i] = Math.min(a, b, c);
        best = Math.max(best, maxDp[i]);
    }
 
    return best;
};

Optimized Solution#

Since each step depends only on the previous step's max and min, compress to rolling variables:

# Python — space-optimized, O(n) time, O(1) space
class Solution:
    def maxProduct(self, nums: list[int]) -> int:
        max_here = min_here = best = nums[0]
        for i in range(1, len(nums)):
            # Must compute new values from OLD max_here and min_here
            candidates = [nums[i], max_here * nums[i], min_here * nums[i]]
            max_here = max(candidates)
            min_here = min(candidates)
            best = max(best, max_here)
        return best

// JavaScript — space-optimized, O(n) time, O(1) space
var maxProduct = function(nums) {
    let maxHere = nums[0], minHere = nums[0], best = nums[0];
    for (let i = 1; i < nums.length; i++) {
        const a = nums[i], b = maxHere * nums[i], c = minHere * nums[i];
        maxHere = Math.max(a, b, c);
        minHere = Math.min(a, b, c);
        best = Math.max(best, maxHere);
    }
    return best;
};

Elegant swap variant: When nums[i] is negative, max and min naturally flip. Some implementations swap max_here and min_here before multiplying, which achieves the same result:

# Python — swap variant, same complexity
class Solution:
    def maxProduct(self, nums: list[int]) -> int:
        max_here = min_here = best = nums[0]
        for n in nums[1:]:
            if n < 0:
                max_here, min_here = min_here, max_here
            max_here = max(n, max_here * n)
            min_here = min(n, min_here * n)
            best = max(best, max_here)
        return best

Visual Dry Run#

Input: nums = [-2, 3, -4]

Answer: 24. The subarray [-2, 3, -4] gives product 24. The minimum at step 1 (-6) became the maximum at step 2 when multiplied by -4.

Input: nums = [2, 3, -2, 4]

Answer: 6. The subarray [2, 3] gives product 6.

Complexity Analysis#

Common Mistakes#

1. Only tracking the maximum, not the minimum. Tracking only max_here misses the case where two negatives multiply to a large positive. Always track both max_here and min_here.

2. Updating max_here before using it to compute min_here. Since both new values depend on the old max_here and min_here, compute the candidates list using the old values first. If you update max_here first and then use the new max_here to compute min_here, the result is wrong.

3. Forgetting the "start fresh" candidate. Candidates must always include nums[i] alone. If you only take max_here * nums[i] and min_here * nums[i], you cannot start a new subarray at the current element.

4. Initializing to 0 instead of nums[0]. As with Maximum Subarray, the subarray must be non-empty. Initialize max_here = min_here = best = nums[0].

5. Assuming zeros kill all future subarrays. After a zero, max_here = min_here = 0, and the next element starts fresh (candidate nums[i] is the tie-breaker). The algorithm handles this correctly without special-casing zeros.

6. Missing the all-negatives case. For [-1, -2, -3], all products: -1, 2, -6, and also subarrays: -2, 6. Max is 6 (subarray [-2, -3]). The algorithm tracks min=-6 at index 2, which when multiplied by -3 gives 18... wait, let us trace: step 0: max=-1, min=-1, best=-1. Step 1: candidates=[-2, 2, 2], max=2, min=-2, best=2. Step 2: candidates=[-3, -6, 6], max=6, min=-6, best=6. Correct.

Interview Tips#

Derive the need for min tracking. Do not just state "we track min and max." Explain why: "A very negative product today can become the largest positive product tomorrow if the next element is negative. So I must track both the running maximum and minimum."

Show the three candidates explicitly. Always list all three candidates: [nums[i], max_here * nums[i], min_here * nums[i]]. This makes the logic transparent and prevents the "update order" bug.

Connect to Maximum Subarray. Say: "This is Kadane's Algorithm adapted for products. Instead of max(nums[i], prev + nums[i]), I track both max and min because multiplication with negative numbers inverts the ordering."

Mention zeros explicitly. Zeros reset both max_here and min_here to 0, and the next element starts fresh. Mention this to show awareness of edge cases.

Follow-up Questions#

Q: What if you need to return the actual subarray, not just the product? Track start, end, and temp_start indices alongside max_here. Update start and end whenever a new best is found.

Q: What if the array can contain zeros and you must find a non-zero product subarray? Split on zeros and run the algorithm on each segment. Return the max across all segments (or 0 if no non-zero elements exist).

Q: What about Maximum Product of Three Numbers (LC 628)? Sort the array and return max(nums[-1]*nums[-2]*nums[-3], nums[0]*nums[1]*nums[-1]). This is O(n log n) but a different problem — no subarray constraint.

Q: What if products can overflow 64-bit integers? Use Python's arbitrary precision integers, or normalize the product at each step (e.g., track sign and log of magnitude separately).

Q: Can you solve this with a prefix/suffix product approach? Yes — multiply prefix products from left to right, resetting at zeros. Do the same from right to left. The maximum over all prefix/suffix products gives the answer. This is an alternative O(n) O(1) approach.

Key Takeaways#

• The key insight: a negative product today can flip to the maximum tomorrow when multiplied by another negative. Track both max_here and min_here at every step.
• Three candidates at each step: start fresh (nums[i]), extend the previous max, extend the previous min. Take max and min of all three.
• Always compute new max_here and min_here from the OLD values of both — never update one before computing the other.
• Initialize max_here = min_here = best = nums[0] (not 0) to handle all-negative and all-negative-with-zeros inputs correctly.
• The "dual-tracking" technique is a direct extension of Kadane's Algorithm and is the canonical approach for O(n) O(1) solution.
• Zeros naturally reset the running products — no special casing required if the candidates always include nums[i] alone.