152. Maximum Product Subarray

Find the contiguous subarray with the largest product and return that product.

A negative number turns the smallest product into the largest. Keep both the max and min product ending at each index.

1function maxProduct(nums: number[]): number {
2  let hi = nums[0], lo = nums[0], best = nums[0];
3  for (let i = 1; i < nums.length; i++) {
4    const x = nums[i];
5    const candidates = [x, hi * x, lo * x];
6    hi = Math.max(...candidates);
7    lo = Math.min(...candidates);
8    best = Math.max(best, hi);
9  }
10  return best;
11}

hi = 2lo = 2best = 2

nums

-2

-1

hi = lo = best = 2.

1 / 0

Space: play/pause · ←/→: step