find maximum product subarray

Medium

Problem

Given an integer array that may contain negatives and zeros, find the contiguous subarray with the largest product and return that product.

Example 1

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

[2, 3] gives 6. Including -2 makes the product negative.

Example 2

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

Two negatives multiply to a positive: the whole array.

Test cases

Case 1

Input:    [2,3,-2,4]
Expected: 6

Case 2

Input:    [-2,0,-1]
Expected: 0

Case 3

Input:    [-2,3,-4]
Expected: 24

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
View solutionHide solution1 approach

1. Track running max and min

Time O(n)Space O(1)

A negative number swaps max and min, so carry both. Best answer is the running max.

function maxProduct(nums) {
let maxP = nums[0], minP = nums[0], res = nums[0];
for (let i = 1; i < nums.length; i++) {
const x = nums[i];
if (x < 0) [maxP, minP] = [minP, maxP];
maxP = Math.max(x, maxP * x);
minP = Math.min(x, minP * x);
res = Math.max(res, maxP);
}
return res;
}