152. Maximum Product Subarray

This looks like Maximum Subarray with × swapped for +, but that one substitution breaks the whole approach. Negatives and zeros make products misbehave in a way sums never do, and the fix is to track two values at once instead of one.

Question

Given an integer array nums, find a subarray that has the largest product, and return the product.
The test cases are generated so that the answer will fit in a 32-bit integer.

Note that the product of an array with a single element is the value of that element.

Example1

Input: nums = [2, 3, -2, 4]
Output: 6
Explanation: [2, 3] has the largest product 6.

Example2

Input: nums = [-2, 0, -1]
Output: 0
Explanation: The result cannot be 2, because [-2, -1] is not a subarray.

Constraints

• $1 <= nums.length <= 2 * 10^4$
• $-10 <= nums[i] <= 10$
• The product of any subarray of nums is guaranteed to fit in a 32-bit integer.

Solution: Space-Optimized Dynamic Programming

• Time Complexity: $O(n)$
• Space Complexity: $O(1)$

public int maxProduct(int[] nums) {
    int max = nums[0];
    int min = nums[0];
    int result = nums[0];

    for (int i = 1; i < nums.length; i++) {
        // If we encounter a negative number, max and min might flip, so swap them first
        if (nums[i] < 0) {
            int temp = max;
            max = min;
            min = temp;
        }

        // The logic becomes much simpler:
        // 1. Compare the previous accumulated value (max * nums[i]) and
        // 2. The current value (nums[i], meaning start fresh)
        max = Math.max(nums[i], max * nums[i]);
        min = Math.min(nums[i], min * nums[i]);

        result = Math.max(result, max);
    }
    return result;
}

Why the sum trick doesn’t transfer

Maximum Subarray gets away with one running best because adding a number nudges the sum in a predictable direction. Products don’t cooperate. Multiply the running product by a negative and the largest value becomes the smallest and the smallest becomes the largest. A lone max can’t survive that flip — a deeply negative product you’d normally discard is a single negative number away from being the biggest product in the array.

Track max and min together

So the code carries both extremes ending at each index. When nums[i] is negative it swaps max and min before extending, precisely because the multiplication is about to invert them. The Math.max(nums[i], max * nums[i]) covers the other reset: a 0 collapses both products to zero, and starting fresh from nums[i] is how the window recovers afterward. That’s why example 2, [-2, 0, -1], returns 0 — the zero severs the array, and nothing after it can climb back over.

Dry Run

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

i	nums[i]	Swap?	max (after)	min (after)	result	Notes
1	3	❌	6	3	6	Positive → product grows
2	-2	✔	-2	-12	6	Negative → swap max/min first
3	4	❌	4	-48	6	Positive → better to start fresh

References

• https://leetcode.com/problems/maximum-product-subarray/