Maximum Product Subarray: Track Min and Max

You are given an integer array nums. Find the contiguous subarray that has the largest product, and return that product.

This is LeetCode 152: Maximum Product Subarray, and it is a natural follow-up to Maximum Subarray. If you solved the sum version with Kadane's algorithm, you might expect the product version to work the same way. It almost does, but there is one critical twist: negative numbers flip signs, and that changes everything.

Why Kadane's algorithm breaks here

In the sum version, if your running sum goes negative you just restart. A negative running sum can never help you because adding a negative to a future element always makes it worse.

Products do not work that way. A very negative running product can become a very positive product if you hit another negative number. Think about it: -12 * -2 = 24. That large negative product was not dead weight. It was a loaded spring waiting for another negative to flip it.

So the "just track the max" approach from Kadane's fails. You need something more.

The key insight: track min and max

At each position, instead of keeping one running value, you keep two:

• max_prod: the largest product of any subarray ending here
• min_prod: the smallest (most negative) product of any subarray ending here

At each new element nums[i], the new max and min can come from three candidates:

1. nums[i] alone (restart the subarray)
2. max_prod * nums[i] (extend the best subarray)
3. min_prod * nums[i] (extend the worst subarray, which flips if nums[i] is negative)

You pick the largest of the three for your new max_prod, and the smallest of the three for your new min_prod. Then update the global result.

That is it. Same single-pass structure as Kadane's, but with two tracking variables instead of one.

Walking through it step by step

Let's trace through nums = [2, 3, -2, 4, -1, 6]. At each step we track max_prod, min_prod, and the global result. Watch what happens when we hit the negative numbers.

The magic moment is step 5. The min_prod of -48 had been sitting there since step 4, looking useless. Then we multiplied by -1 and it became 48, which is the new maximum. Without tracking the minimum, we would have completely missed that.

The brute force approach

Before we look at the optimal solution, here is the brute force for comparison. Check every subarray, compute the product, track the maximum.

def max_product_brute(nums):
    best = nums[0]
    for i in range(len(nums)):
        product = 1
        for j in range(i, len(nums)):
            product *= nums[j]
            best = max(best, product)
    return best

This is O(n^2). It works for small inputs but will not pass LeetCode's time limits on large arrays.

The code

Here is the optimal solution in Python:

def max_product(nums):
    max_prod = nums[0]
    min_prod = nums[0]
    result = nums[0]

    for i in range(1, len(nums)):
        candidates = (nums[i], max_prod * nums[i], min_prod * nums[i])
        max_prod = max(candidates)
        min_prod = min(candidates)
        result = max(result, max_prod)

    return result

Let's walk through what each line does:

1. Initialize max_prod, min_prod, and result to nums[0]. We need at least one element, so the first element is our starting point.
2. For each subsequent element, compute the three candidates: the element alone, the previous max times this element, and the previous min times this element.
3. The new max_prod is the biggest of the three. The new min_prod is the smallest.
4. Update result if the new max_prod is the best we have ever seen.
5. Return result.

Why tracking min matters

This is the part that trips people up. Let's look at a concrete example to really nail it down.

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

• After index 0: max_prod = -2, min_prod = -2, result = -2
• After index 1: candidates are (3, -2*3, -2*3) = (3, -6, -6). So max_prod = 3, min_prod = -6, result = 3
• After index 2: candidates are (-4, 3*(-4), -6*(-4)) = (-4, -12, 24). So max_prod = 24, min_prod = -12, result = 24

The answer is 24, which comes from the product (-2) * 3 * (-4). The two negatives cancel out. If you only tracked the maximum, after index 1 you would have max_prod = 3 and you would compute 3 * (-4) = -12 at index 2. You would completely miss the 24.

The minimum product of -6 is what saved us. It remembered "there is a subarray ending here with product -6", and when the -4 came along, -6 times -4 gave us 24.

This is why the problem is fundamentally different from Maximum Subarray. In the sum version, a negative running sum is always bad. In the product version, a negative running product might be the best thing that ever happened to you.

Handling zeros

There is one more wrinkle: zeros. Any subarray that includes a zero has a product of zero. When you multiply max_prod or min_prod by zero, both become zero.

This actually works out fine with our algorithm. When nums[i] is 0:

• candidates = (0, max_prod * 0, min_prod * 0) = (0, 0, 0)
• max_prod = 0, min_prod = 0

This effectively restarts the subarray at the next element, which is exactly what you want. A zero breaks any product chain.

Complexity analysis

Time: O(n). We visit each element exactly once. Each visit does O(1) work (computing a few products and comparisons).

Space: O(1). Three variables (max_prod, min_prod, result), regardless of input size.

This is optimal. You need to look at every element at least once, so you cannot do better than O(n).

Edge cases to watch for

• All positive like [1, 2, 3, 4]: the entire array is the max product. Product = 24.
• Single negative like [2, -1, 3]: the negative splits the optimal subarray. Answer is 3 (not 2 * -1 * 3 = -6).
• Two negatives like [-2, 3, -4]: the negatives cancel. Answer is 24.
• Contains zero like [0, 2]: the zero forces a restart. Answer is 2.
• All negative like [-2, -3, -4]: the best is (-2) * (-3) = 6. The algorithm handles this because min_prod carries the negative chain.
• Single element [5] or [-3]: return that element.

The building blocks

This problem is built on two reusable patterns:

1. Linear DP with constant state. Just like Maximum Subarray, the recurrence only depends on the previous step. You do not need a full DP array. Two variables (max_prod and min_prod) carry everything forward. This is the same space optimization trick from Climbing Stairs and House Robber.

2. Min/max dual tracking. This is the twist that makes the product version unique. Whenever your operation can flip signs (multiplication by negatives), you need to track both extremes. The minimum at one step can become the maximum at the next. This pattern also appears in problems involving absolute values and interval tracking.

The combination of these two building blocks gives you the full solution: "walk through the array, maintain a running max and min product at each position, and update the global result." Recognize the blocks, and the code writes itself.

From understanding to recall

You have just seen why tracking both the minimum and maximum products is essential, and the logic makes perfect sense right now. But here is the thing: the next time you see this problem on a whiteboard, will you remember to compute candidates before updating max_prod? Will you remember to handle the zero case? Will you remember that min_prod * nums[i] is one of the three candidates?

Spaced repetition is how you bridge the gap between understanding and recall. You revisit the min/max dual tracking pattern at increasing intervals, writing the solution from scratch each time. After a few reps, the three-candidate approach and the initialization become automatic.

The min/max dual tracking pattern and linear DP with constant state are two of roughly 60 reusable building blocks that cover hundreds of LeetCode problems. Drilling them individually with spaced repetition is far more effective than grinding random problems and hoping the patterns stick.

Related posts

• Maximum Subarray - The sum version of this problem, solved with Kadane's algorithm. Same DP skeleton, but you only need to track the max because negative sums are never helpful.
• House Robber - Another linear DP with constant state problem, showing the rob-or-skip decision at each position.