Maximum Product Subarray

return Maximum Product Subarray

Maximum Product Subarray

Problem

Given an integer array nums, find a subarray with the largest product, and return the product.

A subarray is a continuous, non-empty part of the array. The answer always fits in a 32-bit integer. The product of a single element is that element.

Examples

Example 1

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

• The subarray [2,3] has the largest product, which is 6.
• Adding -2 makes the product negative, so it is not helpful.

Example 2

Input: nums = [-2,0,-1]
Output: 0

• The answer cannot be 2, because [-2,-1] is not a subarray. The 0 is between them.
• The best product is 0.

Constraints

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

Main Idea

This looks like Maximum Subarray (sum), but products behave differently because of negative numbers and zeros.

• A negative number flips the sign. A very small (negative) product can become a very big (positive) product when we multiply it by another negative number.
• A zero makes the whole product 0. After a zero, we must start again.

So at each index we keep two values for subarrays that end at this index:

• maxProd: the biggest product.
• minProd: the smallest product (the most negative one).

For a new number x, the best subarray ending here is one of three choices:

• x alone (start a new subarray).
• x * maxProd (extend the biggest product).
• x * minProd (extend the smallest product, which helps when x is negative).

So:

newMax = max(x, x * maxProd, x * minProd)
newMin = min(x, x * maxProd, x * minProd)

The answer is the biggest maxProd seen at any index.

Why keep the minimum? If minProd = -6 and the next number is -2, then x * minProd = 12. Without minProd, we would miss this.

Solution 1: Brute Force

We check every subarray. For each start i, we keep a running product as j moves forward.

var maxProduct = function (nums) {
    let best = -Infinity;

    for (let i = 0; i < nums.length; i++) {
        let product = 1;

        for (let j = i; j < nums.length; j++) {
            product *= nums[j];
            best = Math.max(best, product);
        }
    }

    return best;
};

Complexity

• Time Complexity: O(n²)
  • We check every start and end pair.
• Space Complexity: O(1)
  • We use only a few variables.

Solution 2: Track Max and Min (Optimal)

var maxProduct = function (nums) {
    let maxProd = nums[0];
    let minProd = nums[0];
    let best = nums[0];

    for (let i = 1; i < nums.length; i++) {
        const x = nums[i];

        // save the old values, because both updates need them
        const prevMax = maxProd;
        const prevMin = minProd;

        maxProd = Math.max(x, x * prevMax, x * prevMin);
        minProd = Math.min(x, x * prevMax, x * prevMin);

        best = Math.max(best, maxProd);
    }

    return best;
};

How the Code Works

Step 1: Start with the first number

• maxProd and minProd are the first number. A subarray with one element has only that product.
• best is also the first number.

Step 2: Read each next number x

• We save prevMax and prevMin first. Both new values need the old ones. If we changed maxProd first, then minProd would use a wrong value.

Step 3: Update both values

• maxProd is the biggest of: x alone, x * prevMax and x * prevMin.
• minProd is the smallest of the same three values.

Step 4: Keep the best

• best keeps the biggest maxProd seen so far.

How the cases are handled

• Positive x: x * prevMax is the biggest, and x * prevMin is the smallest.
• Negative x: The roles swap. x * prevMin can become the biggest, and x * prevMax can become the smallest. The three-way max and min handle this without an if.
• Zero x: Both maxProd and minProd become 0. The next number starts fresh, because x alone is one of the choices.

Dry Run

Let us take nums = [2, 3, -2, 4].

The answer is 6.

Now let us take nums = [-2, 3, -4], where two negatives help.

The answer is 24, from the whole array. The old minimum -6 times -4 gave the big result.

Complexity

• Time Complexity: O(n)
  • We go through the array once.
• Space Complexity: O(1)
  • We use only a few variables.

Solution 3: Prefix and Suffix Products (Optional)

Another way uses this fact: in the best subarray, if there are no zeros, the answer is either a prefix or a suffix of the zero-free part (when the count of negatives is odd, we drop everything up to the first or after the last negative).

So we scan from the left and from the right, keep a running product, and reset it to 1 after a zero.

var maxProduct = function (nums) {
    let best = -Infinity;
    let prefix = 1;
    let suffix = 1;
    const n = nums.length;

    for (let i = 0; i < n; i++) {
        // restart after a zero
        prefix = (prefix === 0 ? 1 : prefix) * nums[i];
        suffix = (suffix === 0 ? 1 : suffix) * nums[n - 1 - i];

        best = Math.max(best, prefix, suffix);
    }

    return best;
};

• prefix is the running product from the left. suffix is the running product from the right.
• When a product becomes 0, we reset it to 1 before the next multiplication, so a zero acts as a wall.
• Time Complexity: O(n). Space Complexity: O(1).

Comparison

Summary

• Products are tricky, because a negative number can flip the smallest value into the biggest.
• At each index, we track both the maximum and the minimum product of subarrays ending there.
• The new values come from three choices: x alone, x * prevMax and x * prevMin.
• Save the old values first, then update both.
• A zero resets everything, because x alone is always a choice.
• The optimal solution runs in O(n) time and uses O(1) space.