139. Maximum Product Subarray

A negative number flips the sign, so today's smallest (most negative) product can become tomorrow's largest. Carry both the max and the min ending at each index.

Why track the minimum too?

With only positives, a running maximum product (like Kadane's) is enough. But a negative number turns the largest product into the smallest and vice-versa. So the most-negative product so far matters: multiplied by another negative it may become the new maximum.

At each element x, the best product ending here is one of three things:

• x alone (start fresh),
• x * curMax (extend the previous best),
• x * curMin (a big negative flipped positive).

curMax = max(x, x*curMax, x*curMin)
curMin = min(x, x*curMax, x*curMin)
result = max(result, curMax)

Worked example

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

The subarray [2,3,-2,4,-1] yields the answer 48.

Complexity

• Time: O(n) — single pass.
• Space: O(1) — two rolling variables.

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