Maximum Product Subarray

The problem. Given an integer array nums, find the contiguous subarray with the largest product and return that product.

Example

nums = [2, 3, -2, 4]      ->  6     ([2, 3])
nums = [-2, 0, -1]        ->  0
nums = [2, 3, -2, 4, -1]  ->  48    (the whole array: two negatives cancel)
nums = [-2, 3, -4]        ->  24

The pattern: a small state machine per index

Pattern 5 problems carry more than one number per position: here the best and the worst product ending at i; in the stock problem, holding / just sold / resting; in the interval problems, a whole range [i, j]. The trick is always to find the few states that make the next step decidable.

The idea: the smallest product matters too

For sums, Kadane's algorithm keeps one number: the best sum ending here. Products break that: a big negative product is one negative number away from being the biggest positive one. So keep two: hi, the largest product of a subarray ending at i, and lo, the smallest. For the next number x, the new extremes come from three candidates — x alone, hi · x and lo · x. When x is negative, the old lo produces the new hi, so just swap them first. A zero resets both to 0, and the next number starts fresh.

1. Every subarray

1function maxProduct(nums) {2  let best = -Infinity;3  for (let i = 0; i < nums.length; i++) {4    let product = 1;5    for (let j = i; j < nums.length; j++) {6      product *= nums[j];                        // product of nums[i..j]7      best = Math.max(best, product);8    }9  }10  return best;11}

Time O(n²), space O(1). Each start extends its product one number at a time instead of recomputing it.

2. Largest and smallest ending here

1function maxProduct(nums) {2  let hi = nums[0], lo = nums[0], best = nums[0];   // largest and smallest product ending here3  for (let i = 1; i < nums.length; i++) {4    const x = nums[i];5    if (x < 0) [hi, lo] = [lo, hi];              // a negative turns the smallest into the largest6    hi = Math.max(x, hi * x);                    // start fresh at x, or extend7    lo = Math.min(x, lo * x);8    best = Math.max(best, hi);9  }10  return best;11}

Time O(n), space O(1). This is the DP: two states per index, each computed from the two before it. It's the answer to give.

3. Prefix and suffix products

Another way to see it. Inside a stretch with no zeros, if the count of negatives is even, the whole stretch is best. If it's odd, you must drop one negative — and everything on one side of it — so the best is a prefix or a suffix of the stretch. Scanning from both ends, and restarting after each zero, sees all of them.

1function maxProduct(nums) {2  const n = nums.length;3  let best = -Infinity, left = 1, right = 1;4  for (let i = 0; i < n; i++) {5    left = (left === 0 ? 1 : left) * nums[i];              // prefix product, restarting after a zero6    right = (right === 0 ? 1 : right) * nums[n - 1 - i];   // suffix product, the same from the right7    best = Math.max(best, left, right);8  }9  return best;10}

Time O(n), space O(1). Short and clever, but harder to justify on the spot than the hi/lo version.

Comparing the approaches

Edge cases to test

Variations