Maximum Product Subarray

Interview Prep

StandardDynamic Programming Variation of Maximum Subarrayarraysdp

The problem

Given an integer array, return the largest product of any contiguous non-empty subarray. Same shape of question as Maximum Subarray, but with multiplication instead of addition — and that one change completely breaks the standard Kadane recurrence.

Why naive Kadane fails

Kadane's recurrence assumes that "extending the previous best" or "restarting fresh" are the only two candidates. For sums, that's true: extending a running sum is monotonic in the existing sum's sign. For products it isn't — a strongly negative running product can become the new maximum if multiplied by another negative. Tracking only the running max misses this entirely.

def max_product_wrong(nums):
    """Naive Kadane-style: track only the max running product.  WRONG when negatives appear."""
    best = current = nums[0]
    for x in nums[1:]:
        current = max(x, current * x)        # ignores the possibility of a big-negative flip
        best = max(best, current)
    return best
# nums = [-2, 3, -4]
# i=1: current = max(3, -2*3=-6) = 3.    best=3.
# i=2: current = max(-4, 3*-4=-12) = -4. best=3.
# Wrong: the actual best is (-2)*3*(-4) = 24.

Pattern: track min and max simultaneously

The fix is to maintain both cur_max and cur_min running products ending at the current position. At each step, the new max is the largest of { x, cur_max·x, cur_min·x }; symmetrically the new min is the smallest. Multiplying by a negative x swaps which one yesterday's min/max contributes to.

The "always include x alone in the candidate set" detail is the equivalent of Kadane's restart move — it accounts for the case where every previous product is worse than just starting over at the current position.

Solution

def max_product_subarray(nums: list[int]) -> int:
    """Track BOTH the running min and the running max.
    A large-magnitude negative becomes a large-magnitude positive when multiplied by another negative.
    """
    best = cur_max = cur_min = nums[0]
    for x in nums[1:]:
        # If x is negative, its product flips signs: yesterday's min becomes the new max candidate.
        # Compute both fresh from {x, cur_max*x, cur_min*x}.
        candidates = (x, cur_max * x, cur_min * x)
        cur_max = max(candidates)
        cur_min = min(candidates)
        best = max(best, cur_max)
    return best

Trace

nums = [-2, 3, -4]

init:        best = cur_max = cur_min = -2.

i=1, x=3:    candidates = (3, -2*3=-6, -2*3=-6).
             cur_max = 3, cur_min = -6.
             best = max(-2, 3) = 3.

i=2, x=-4:   candidates = (-4, 3*-4=-12, -6*-4=24).
             cur_max = 24, cur_min = -12.
             best = max(3, 24) = 24.

return 24

Zeros reset everything

nums = [2, 0, 3, -1, 4]

init: best=cur_max=cur_min=2.
i=1, x=0:    candidates = (0, 0, 0). cur_max=0, cur_min=0. best=max(2, 0)=2.
i=2, x=3:    candidates = (3, 0, 0). cur_max=3, cur_min=0. best=3.
i=3, x=-1:   candidates = (-1, -3, 0). cur_max=0, cur_min=-3. best=3.
i=4, x=4:    candidates = (4, 0, -12). cur_max=4, cur_min=-12. best=max(3, 4)=4.

return 4   (subarray [3, -1, 4]? no — that's -12. Best is [4] alone, or [2] alone.)

Zeros behave like resets — both cur_max and cur_min collapse to 0, and the
next non-zero element starts a fresh segment.

Complexity

Time: O(n).
Space: O(1).

The general lesson

"Track both extremes" is the canonical trick for any DP where the update rule is not monotone in its input — products, XOR sums, multiplicative dynamic systems. Whenever a value can flip the sign of its accumulator, you need both endpoints of the running range to know the best update at the next step.