Maximum Product Subarray

medium array dp

Problem

Given an integer array nums, find a contiguous non-empty subarray that has the largest product, and return that product.

A negative number flips signs, so the smallest (most negative) running product can suddenly become the largest. Carry both, and at every index reset to the current value if the prefix product would hurt us.

Inputnums = [2, 3, -2, 4]

Output6

The subarray [2, 3] has the largest product, 6.

nums (comma-separated)

def max_product(nums):
    cur_max = cur_min = best = 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)
        best = max(best, cur_max)
    return best

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

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

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

Explanation

This is like the classic "max sum" scan, but with a twist: a negative number flips signs. A tiny, very negative running product can suddenly become the largest if it gets multiplied by another negative. So tracking only the maximum isn't enough — we also track the minimum.

We carry two values as we walk the array: cur_max (best product ending here) and cur_min (worst, most-negative product ending here). When the current number x is negative, we swap them, because multiplying by a negative turns the smallest into the largest and vice versa.

Then we update: cur_max = max(x, cur_max * x). The x option means "start a fresh subarray here" if extending the old product would only hurt. We do the mirror for cur_min, and update best with the running maximum.

Example: [2, 3, -2, 4]. After 2,3 we have cur_max = 6. At -2 we swap, and products dip negative. At 4, cur_max recovers but never beats the earlier 6.

So best = 6. Keeping both extremes is exactly what lets a sign flip work in our favor.

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