Problem
Given an integer array nums, find the contiguous subarray within an array (containing at least one number) which has the largest product.
Example 1:
Input: [2,3,-2,4]
Output: 6
Explanation: [2,3] has the largest product 6.
Example 2:
Input: [-2,0,-1]
Output: 0
Explanation: The result cannot be 2, because [-2,-1] is not a subarray.
Solution
/**
* @param {number[]} nums
* @return {number}
*/
var maxProduct = function(nums) {
if (!nums.length) return 0;
var localMax = 0;
var localMin = 0;
var lastMax = nums[0];
var lastMin = nums[0];
var max = nums[0];
for (var i = 1; i < nums.length; i++) {
localMax = Math.max(lastMax * nums[i], lastMin * nums[i], nums[i]);
localMin = Math.min(lastMax * nums[i], lastMin * nums[i], nums[i]);
max = Math.max(max, localMax);
lastMax = localMax;
lastMin = localMin;
}
return max;
};
Explain:
nope.
Complexity:
- Time complexity : O(n).
- Space complexity : O(1).