find maximum product subarray
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
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;}