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).