Maximum Product Subarray

1. Define the problem

Given an integer array nums, find a contiguous subarray (containing at least one number) which has the largest product, and return that product. A negative number can flip the sign of everything after it, so a single running maximum is not enough. Track two running values at once a running max and a running min ending at the current index, and swap them whenever the current number is negative , since the smallest (most negative) product can become the largest after one more negative multiply.

Constraints

1 ≤ nums.length ≤ 2 × 10⁴
-10 ≤ nums_i ≤ 10
The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer

Example

Inputnums = [2, 3, -2, 4]

Output6

Explanation The subarray [2, 3] has the largest product: 6.

2. Know the words first

In plain terms

Contiguous subarray: A run of elements taken from the array back-to-back, with nothing skipped.

3. Visualize the solution

Track a running max and min, swapping on a negative number

2-2

Statusmax: 2 · min: 2 · best: 2

Seed the running max, running min, and best-so-far with the first element, 2.

What happens in this step

nums[0] = 2

maxProd = minProd = best = 2

Seed all three running values with the first element.

Step 1 of 5

Steps to visualize

The row is the input array, [2, 3, -2, 4]. The frame marks the best subarray found so far.
Seed the running max, running min, and best-so-far with the first element.
At each later index, if the current number is negative, swap the running max and running min.
Update the running max to the larger of the current number alone or the running max times the current number, and the running min similarly.
Update the best-so-far if the running max improved on it.

4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

Track a running max and min, swapping on a negative number

2-2

Statusmax: 2 · min: 2 · best: 2

Seed the running max, running min, and best-so-far with the first element, 2.

What happens in this step

nums[0] = 2

maxProd = minProd = best = 2

Seed all three running values with the first element.

Step 1 of 5

5. Solution

Solution

solution.tsTypeScript

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

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

    if (num < 0) {
      const temp = maxProd;
      maxProd = minProd;
      minProd = temp;
    }

    maxProd = Math.max(num, maxProd * num);
    minProd = Math.min(num, minProd * num);
    best = Math.max(best, maxProd);
  }

  return best;
}

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

6. Test cases

Test cases

Input	Expected	Covers
`nums = [2, 3, -2, 4]`	`6`	example from the docstring
`nums = [-2, 0, -1]`	`0`	a zero breaks any run into pieces, and is itself a valid answer
`nums = [-2, -3, -4]`	`12`	an odd number of negatives — the best product excludes one of them
`nums = [5]`	`5`	smallest valid input, a single positive element
`nums = [-5]`	`-5`	smallest valid input, a single negative element
`nums = [0, 2]`	`2`	a leading zero followed by a positive value
`nums = [-1, -2, -3, -4]`	`24`	an even number of negatives — the whole array is the best product
`nums = [-2, 3, -4]`	`24`	two sign flips across the full array produce the largest product

Maximum Product Subarray