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