Original link: leetcode-cn.com/problems/ma…

Answer:

  1. The subarray contains at least one element, meaning that NUMs [I] must exist in the subarray.

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

  3. 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 arraymaxProductsIn the.
    • nums[i]Smaller value multiplied by the previous subarray, stored in the arrayminProductsIn the.
    • nums[i]Instead of multiplying the previous subarray, it’s going to be the result itself.
  4. 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
  1. iThe state is only withi - 1About,maxProductsandminProductsIt 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