Maximum Product Subarray: Why You Track Both Max and Min

To find the maximum product subarray in O(n) time and O(1) space, scan the array once and keep two values at each position: the largest and the smallest product of any subarray ending there. You need the smallest one because multiplying by a negative number turns the most negative product into the most positive one. The answer is the largest “max ending here” you see.

The problem

Given an integer array nums, find a contiguous, non-empty subarray with the largest product and return that product (not the subarray). This is LeetCode 152. The array can hold positives, negatives and zeros. Examples:

• [2, 3, -2, 4] returns 6 (the subarray [2, 3]).
• [-2, 0, -1] returns 0. Neither -2 nor -1 beats it, and you cannot skip the zero to combine them because the subarray must be contiguous.
• [-2, 3, -4] returns 24, the whole array: two negatives cancel out.

Brute force: O(n^2)

Start at every index, extend to the right, and keep a running product. Track the best value seen.

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 correct, uses O(1) extra space, and takes O(n^2) time. It is a fine first answer in an interview because it is easy to verify, and it gives you a reference to test the faster version against.

Why the maximum product alone is not enough

The maximum subarray sum problem (Kadane’s algorithm) keeps one number: the best sum ending at the current index. If it is negative, you drop it and start fresh. Products behave differently. Look at [-2, 3, -4]:

• The best product ending at 3 is 3, because -2 * 3 = -6 is worse than starting over.
• If you only kept that 3, you would compute 3 * -4 = -12 and conclude the answer is 3.
• The real answer is (-2) * 3 * (-4) = 24. The bad-looking -6 was worth keeping, because the next negative number flips it to 24.

So at every index you remember two things about the subarrays that end there: the largest product and the smallest (most negative) product. A negative number swaps their roles: the old minimum times a negative becomes the new maximum.

The O(n) solution

For each new number x, the best subarray ending at x is one of three things:

1. x alone (start a new subarray here, which also handles zeros),
2. x times the previous maximum,
3. x times the previous minimum.

The new maximum is the largest of the three and the new minimum is the smallest. Compute both from the same old values before overwriting either one.

def max_product(nums):
    cur_max = cur_min = result = nums[0]
    for x in nums[1:]:
        candidates = (x, cur_max * x, cur_min * x)
        cur_max, cur_min = max(candidates), min(candidates)
        result = max(result, cur_max)
    return result

print(max_product([2, 3, -2, 4]))   # 6
print(max_product([-2, 0, -1]))     # 0
print(max_product([-2, 3, -4]))     # 24
print(max_product([-2]))            # -2

Building a tuple of candidates first avoids the classic bug of updating cur_max and then using the already-changed value to compute cur_min. Time is O(n), space is O(1).

A worked trace

Take nums = [2, 3, -2, 4, -1]. Both values start at 2. Each row shows the state after processing x:

x	candidates (x, max*x, min*x)	cur_max	cur_min	result
2 (start)	–	2	2	2
3	3, 6, 6	6	3	6
-2	-2, -12, -6	-2	-12	6
4	4, -8, -48	4	-48	6
-1	-1, -4, 48	48	-4	48

Watch the last row. After 4, the maximum is only 4, but the minimum -48 is the product of the whole prefix 2 * 3 * -2 * 4. The final -1 flips it into 48, the answer. A solution that tracked only the maximum would return 6.

Now a zero. For [-2, 0, -1]: start at -2. At 0 every candidate is 0, so max and min both become 0 and the old product is wiped out. At -1 the candidates are -1, 0, 0, so max is 0, min is -1, and the result stays 0. No special zero handling is needed because “x alone” is always a candidate.

Variant: swap instead of computing three candidates

Many write-ups use an equivalent form. If x is negative, swap the max and min first, then multiply:

def max_product_swap(nums):
    cur_max = cur_min = result = nums[0]
    for x in nums[1:]:
        if x < 0:
            cur_max, cur_min = cur_min, cur_max
        cur_max = max(x, cur_max * x)
        cur_min = min(x, cur_min * x)
        result = max(result, cur_max)
    return result

It does the same thing: after the swap, the old minimum sits in cur_max, so multiplying by a negative x gives the larger value. The three-candidate version is harder to get wrong, so it is the safer one to write under pressure.

Another way: prefix and suffix products

There is a second O(n) idea. Within a stretch of the array without zeros, the best subarray is either the whole stretch (an even number of negatives) or it drops a prefix or a suffix up to the first or last negative number. So the best product is always a prefix product or a suffix product of some zero-free stretch. Walk the array from both ends at once, reset the running product to 1 after a zero, and take the maximum over everything you see:

def max_product_prefix_suffix(nums):
    best = nums[0]
    prefix = suffix = 1
    for i in range(len(nums)):
        prefix = (prefix or 1) * nums[i]
        suffix = (suffix or 1) * nums[-1 - i]
        best = max(best, prefix, suffix)
    return best

The (prefix or 1) trick restarts the product after a zero. This version is short, but the reasoning behind it is harder to explain, so the max/min version is usually the better choice in an interview.

Test it against the brute force

All four functions above pass these cases, plus 20,000 random arrays of length 1 to 9 with values from -4 to 4, and they agree with the brute force. Good hand-written cases to include:

cases = [
    ([2, 3, -2, 4], 6),
    ([-2, 0, -1], 0),
    ([-2, 3, -4], 24),
    ([0, 2], 2),
    ([-2, -3, -4], 12),
    ([-3], -3),               # single negative element
    ([-1, -1], 1),
    ([0, 0], 0),
    ([1, 0, -1, 2, 3, -5, -2], 60),
]
for nums, expected in cases:
    assert max_product(nums) == expected, nums
print("all passed")

Common mistakes

• Tracking only the maximum. It fails on [-2, 3, -4], where the answer depends on a negative product you would have thrown away.
• Overwriting before using. Setting cur_max and then computing cur_min from the new cur_max gives wrong results. Compute both from the old values.
• Starting from 1 or 0. Initialize with nums[0]. If you start result at 0, an input like [-3] returns 0 instead of -3.
• Forgetting “x alone”. Without it, a zero (or a fresh start after one) never resets the chain properly.
• Dividing to slide a window. Some solutions try to update a product by dividing out the element that leaves. That breaks as soon as a zero is in the window. Fixed-length windows need a different approach (rebuild the product, or split the array at zeros).
• Overflow. In C++ or Java the intermediate products can overflow. The LeetCode statement guarantees that the answer fits in a 32-bit integer, but intermediate values such as the running minimum can still be large, so use 64-bit integers there. Python integers do not overflow.

What an interviewer may ask next

• Why is it correct? Any subarray ending at index i is a subarray ending at i - 1 extended by nums[i], or just nums[i]. The product of the extended one is monotone in the old product: if nums[i] is positive, the largest old product gives the largest new one; if negative, the smallest does. So only the extremes matter.
• What about the maximum sum version? That is Kadane’s algorithm with a single value. You can practice it in the Maximum Sum Subarray lesson, and the second version takes it further with partial sums.
• Can you return the subarray itself? Yes. Remember where the current candidate started (reset the start index whenever “x alone” wins, and update the best start and end when result improves). The extra state does not change the complexity.
• Complexity? O(n) time, O(1) extra space. You cannot do better than O(n) because every element can change the answer.
• What if the array is empty? The LeetCode problem guarantees at least one element. In an interview, ask, and agree on what to return before you code.

If you want more array problems with step-by-step hints, you can try them in the AlgoCademy app. The same two-state idea (keep the best and the worst ending at each index) shows up in other dynamic programming problems, so it is worth being able to explain it without notes.