Maximum Product Subarray

Approach Summary

Track both max and min products ending at i (negatives can flip sign). maxProd[i] = max(nums[i], maxPrev×nums[i], minPrev×nums[i]).

Full Solution & Approach

A contiguous subarray with the maximum product is not found the way a maximum-sum subarray is, because a single negative number can flip a large positive product into a large negative one — and two negatives can flip it right back. So the classic Kadane-style single running value is not enough; the correct DP keeps two running values at every position: the maximum product of any subarray ending here and the minimum product of any subarray ending here. When the current element is negative, the roles swap — multiplying by a negative turns the previous maximum into the new minimum candidate and vice versa, so the algorithm swaps the two running values before combining. Then the new max is the largest of (current element alone, max_so_far × current), and the new min is the smallest of (current element alone, min_so_far × current). Keeping the current element alone handles the reset case where starting a fresh subarray beats extending the old one — which is also what makes the answer correct when a zero appears, since the zero truncates every subarray that crosses it. The global answer is the largest max_so_far seen at any position. This runs in a single pass and is the canonical hard-ish follow-up to Maximum Subarray.

One pass over the array with constant work per element — O(n) time. Only three running values plus the global best, so O(1) space.

Solution Code

Solution

def max_product(nums: list[int]) -> int:
    best = nums[0]
    cur_min = cur_max = nums[0]
    for n in nums[1:]:
        if n < 0:
            cur_min, cur_max = cur_max, cur_min
        cur_max = max(n, cur_max * n)
        cur_min = min(n, cur_min * n)
        best = max(best, cur_max)
    return best

function maxProduct(nums) {
  let best = nums[0];
  let curMin = nums[0], curMax = nums[0];
  for (let i = 1; i < nums.length; i++) {
    const n = nums[i];
    if (n < 0) [curMin, curMax] = [curMax, curMin];
    curMax = Math.max(n, curMax * n);
    curMin = Math.min(n, curMin * n);
    best = Math.max(best, curMax);
  }
  return best;
}

public int maxProduct(int[] nums) {
    int best = nums[0];
    int curMin = nums[0], curMax = nums[0];
    for (int i = 1; i < nums.length; i++) {
        int n = nums[i];
        if (n < 0) { int tmp = curMin; curMin = curMax; curMax = tmp; }
        curMax = Math.max(n, curMax * n);
        curMin = Math.min(n, curMin * n);
        best = Math.max(best, curMax);
    }
    return best;
}

int maxProduct(const vector<int>& nums) {
    int best = nums[0];
    int curMin = nums[0], curMax = nums[0];
    for (int i = 1; i < (int)nums.size(); i++) {
        int n = nums[i];
        if (n < 0) swap(curMin, curMax);
        curMax = max(n, curMax * n);
        curMin = min(n, curMin * n);
        best = max(best, curMax);
    }
    return best;
}

Edge Cases to Watch

All negative numbers — the best is the largest single element (e.g. [-2,-3,-4] → -2)
A zero in the middle — subarrays cannot cross it, so the answer lies entirely on one side
Single element — the answer is that element
Negative products — the min-tracking correctly handles the sign flip

How to Recognize This Pattern

Negative × negative = positive — track min alongside max
Kadane's variant with two running products

Complexity Analysis

Time Complexity

O(n)

Space Complexity

O(1)