Maximum Product Subarray

Examples

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

The subarray [2, 3] has product 6, which beats any subarray that includes the -2.

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

Any subarray touching the 0 gives a product of 0, and no other subarray beats that (the lone -2 or -1 are both negative).

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

The whole array multiplies to (-2) * 3 * (-4) = 24 — the two negatives cancel out.

Constraints

• 1 <= nums.length <= 2 * 10^4

• -10 <= nums[i] <= 10

Approach

With a maximum sum subarray, you'd only ever need to track the best sum ending at each position, because adding a number never makes a good running sum suddenly bad. Products break that assumption: multiplying by a negative number flips signs, so the smallest (most negative) running product can suddenly become the largest once you multiply it by another negative.

So at every position, track two running values instead of one: the maximum product of a subarray ending there, and the minimum. When you move to the next number, the new maximum is the best of "start fresh with just this number," "extend the previous max," or "extend the previous min" (in case this number is negative and flips it into something big). Do the same for the new minimum, and keep a separate running answer that records the largest maximum seen at any position.

Solutions

Brute Force — Check Every Subarray

Compute the product of every contiguous subarray directly and keep track of the largest one seen.

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

  for (let i = 0; i < nums.length; i++) {
    let product = 1;
    for (let j = i; j < nums.length; j++) {
      product *= nums[j];
      if (product > best) best = product;
    }
  }

  return best;
}

Time: O(n^2) · Space: O(1)

Optimal — Track Running Max and Min

Sweep through once, carrying forward both the max and min product ending at the current position, since a negative number can turn the running min into the new max.

function maxProduct(nums) {
  let maxEndingHere = nums[0];
  let minEndingHere = nums[0];
  let best = nums[0];

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

    if (num < 0) {
      // A negative number swaps the roles of the running max and min.
      [maxEndingHere, minEndingHere] = [minEndingHere, maxEndingHere];
    }

    maxEndingHere = Math.max(num, maxEndingHere * num);
    minEndingHere = Math.min(num, minEndingHere * num);

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

  return best;
}

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