Original link: leetcode-cn.com/problems/ma…
Answer:
-
The subarray contains at least one element, meaning that NUMs [I] must exist in the subarray.
-
Nums [I] may form subarrays with elements before or after it. If traversing backwards, the subarray elements nums[I] through nums[I + j] will be processed when traversing through nums[I + j]. Therefore, the traversal only needs to consider the combination of nums[I] and its previous elements.
-
Since nums has both positive and negative numbers, the subarray scores before NUMs [I] also have both positive and negative numbers. But the product of negative numbers is positive and can be a maximum, so it needs to be preserved. So the product of each position has 3 possibilities:
nums[i]
The larger value multiplied by the previous subarray is stored in the arraymaxProducts
In the.nums[i]
Smaller value multiplied by the previous subarray, stored in the arrayminProducts
In the.nums[i]
Instead of multiplying the previous subarray, it’s going to be the result itself.
-
MaxProducts [I] = math.max (Max, maxProducts[I]); .
/ * * *@param {number[]} nums
* @return {number}* /
var maxProduct = function (nums) {
let max = nums[0]; // Stores the largest product of subarrays. Default is the first item
// Since the product can be negative and negative, we need to store both the maximum and minimum values
// This avoids storing only the maximum value, resulting in negative values being discarded
// However, both minProducts and maxProducts may have negative values
let minProducts = [max]; // Use an array to store the calculated minimum
let maxProducts = [max]; // Use an array to store the calculated maximum value
// Count the maximum product
// Count the maximum product
for (let i = 1; i < nums.length; i++) {
For nums[I], it must be computed into the product, but its previously known product can be discarded
// Calculate the current maximum and minimum product, respectively, assuming that the maximum and minimum values of the previous step are needed
const currMin = minProducts[i - 1] * nums[i];
const currMax = maxProducts[i - 1] * nums[i];
// Compare currMin and currMax with the current values to find the true maximum and minimum values for the position of I
minProducts[i] = Math.min(currMin, currMax, nums[i]);
maxProducts[i] = Math.max(currMin, currMax, nums[i]);
// Compare the current maximum value to find the maximum product in the entire array
max = Math.max(max, maxProducts[i]);
}
return max;
};
Copy the code
i
The state is only withi - 1
About,maxProducts
andminProducts
It can be reduced to variables.
/ * * *@param {number[]} nums
* @return {number}* /
var maxProduct = function (nums) {
let max = nums[0];
// Stores the largest product of subarrays. Default is the first item
// Since the product can be negative and negative, we need to store both the maximum and minimum values
// This avoids storing only the maximum value, resulting in negative values being discarded
PrevMin and prevMax can both have negative values
let prevMin = max;
let prevMax = max;
// Count the maximum product
for (let i = 1; i < nums.length; i++) {
For nums[I], it must be computed into the product, but its previously known product can be discarded
// Calculate the current maximum and minimum product, respectively, assuming that the maximum and minimum values of the previous step are needed
const currMin = prevMin * nums[i];
const currMax = prevMax * nums[i];
// Compare currMin and currMax with the current values to find the true maximum and minimum values for the position of I
prevMin = Math.min(currMin, currMax, nums[i]);
prevMax = Math.max(currMin, currMax, nums[i]);
// Compare the current maximum value to find the maximum product in the entire array
max = Math.max(max, prevMax);
}
return max;
};
Copy the code