Given an integer array nums, find the contiguous subarray with the largest product (that subarray contains at least one number).
The sample1: Input: [2.3.2 -.4] output:6Explanation: Subarray [2.3] has maximum product6.Copy the code
The sample2: Input: [2 -.0.- 1] output:0Explanation: The result cannot be2Because [2 -.- 1] is not a subarray.Copy the code
Answer:
- The current maximum value is calculated as the number group is traversed and constantly updated
- Imax = Max (imax * nums[I], nums[I])
- And since there are negative numbers, that will cause the largest to become the smallest, and the smallest to become the largest. Imin = min(imin * nums[I], nums[I])
- When negative numbers appear, IMAX and IMin exchange for the next step in calculating the time complexity: O(n)
/** * @param {number[]} nums * @return {number} */
var maxProduct = function(nums) {
let dp_min = nums[0].// Record the largest subarray product
dp_max = nums[0].// Record the smallest array product
res = nums[0];
for (var i = 1; i < nums.length; i++) {
var n = nums[i]; // Current element
var min = Math.min(Math.min(dp_min * n, dp_max * n), n); // Dynamically update the minimum value
var max = Math.max(Math.max(dp_max * n, dp_min * n), n); // Dynamically update the maximum value
dp_min = min; // Record the minimum value of i-1
dp_max = max; // Record the maximum value of i-1
res = Math.max(res, dp_max); // Find the maximum value
}
return res
};
Copy the code
This article is formatted using MDNICE