Maximum Product Subarray (LeetCode 152)

The problem

Given an integer array nums (at least one element; values may be negative or zero), return the largest product of any contiguous, non-empty subarray.

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

The subarray [2, 3] has product 6. Including -2 makes the product negative, and [4] alone is only 4.

How to think about it

Start with brute force. Try every start and extend to every end, multiplying as you go: O(n²). It works, but the obvious speed-up, Kadane’s “extend or restart” from Maximum Subarray, breaks if you only track the maximum.

Why plain Kadane fails. With sums, a bad prefix is just a negative number you can drop. With products, a very negative running product is not useless: multiply it by another negative and it becomes the largest value. For [-2, 3, -4], the best is the whole array (24), but a max-only scan would have thrown away -6 after the 3.

The key insight: carry both extremes. At each element x, the best product ending here is one of three things: x alone, cur_max * x, or cur_min * x. The same three candidates also give the new minimum. So keep cur_max and cur_min together, and update both from the same triple before moving on. Track the best cur_max ever seen.

Which pattern is this? 1-D DP with a two-value state (a variant of Kadane). The tell is “best contiguous product”: sign flips mean the worst value so far can become the best one later.

Approach

1. Set best, cur_max and cur_min to nums[0].
2. For each later x: form the candidates (x, cur_max * x, cur_min * x). Set cur_max to their max and cur_min to their min. Update best = max(best, cur_max).
3. Return best.

Solution

def max_product(nums):
    best = cur_max = cur_min = nums[0]
    for x in nums[1:]:
        cands = (x, cur_max * x, cur_min * x)     # restart, or extend the max or the min
        cur_max = max(cands); cur_min = min(cands); best = max(best, cur_max)
    return best
# max_product([2,3,-2,4]) -> 6

Dry run

On [2, 3, -2, 4]:

The best product seen is 6. On [-2, 3, -4] the min carries -6 forward and the answer is 24.

Complexity

• Time: O(n). One pass with constant work per element.
• Space: O(1). Three running values.

Edge cases and pitfalls

• Zeros reset everything: both candidates through a zero become 0, and x alone restarts the run on the next element. [-2, 0, -1] returns 0.
• Updating cur_max before computing cur_min from it uses the wrong value. Build the candidate tuple first, as the code does.
• Single negative element ([-3]) returns -3; don’t initialise best to 0 or 1.
• Overflow isn’t an issue in Python, but in Java or C++ long runs of large values can overflow 32-bit integers.

Related problems

• Maximum Subarray (LeetCode 53): the sum version, where tracking the max alone is enough.
• Product of Array Except Self (LeetCode 238): another product scan, using prefix and suffix products.
• Best Time to Buy and Sell Stock (LeetCode 121): a one-pass scan that carries a running extreme.