LeetCode题解：152. 乘积最大子数组，动态规划，JavaScript，详细注释

[chencl1986]

原题链接：https://leetcode-cn.com/problems/maximum-product-subarray/

解题思路：

1. 子数组至少包含一个元素，意味着nums[i]必然存在于子数组中。

2. nums[i]可能与它之前或者之后的元素组成子数组。如果从前往后遍历，子数组元素为nums[i]到nums[i + j]的情况，会在遍历到nums[i + j]的时候一起处理。因此遍历时只需要考虑nums[i]与其之前元素的组合情况即可。

3. 由于nums中的数字有正有负，那么nums[i]之前的子数组成绩也有正有负。但负数的乘积为正，也有可能成为最大值，因此需要保留。那么每个位置的乘积有3种情况：

   • nums[i]与之前子数组的乘积较大值，将其保存在数组maxProducts中。
   • nums[i]与之前子数组的乘积较小值，将其保存在数组minProducts中。
   • nums[i]不与之前的子数组相乘，它自己作为结果。

4. 位置i的最大值，只需要对比maxProducts[i]和nums[i]即可，状态转移方程为：max = Math.max(max, maxProducts[i]);。

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxProduct = function (nums) {
  let max = nums[0]; // 存储子数组的最大乘积，默认为第一项
  // 由于乘积可能会出现负负得正的情况，因此需要同时存储最大和最小值
  // 这样能避免只存储最大值，导致负值被抛弃的情况
  // 但实际上minProducts和maxProducts都可能存在负值
  let minProducts = [max]; // 使用数组存储已计算出的最小值
  let maxProducts = [max]; // 使用数组存储已计算出的最大值

  // 遍历数组，计算最大乘积
  // 遍历数组，计算最大乘积
  for (let i = 1; i < nums.length; i++) {
    // 对于nums[i]来说，它一定会被计算到乘积中，但它之前已知的乘积是可以被抛弃的
    // 假设上一步的最大值和最小值需要使用，分别计算当前的最大和最小乘积
    const currMin = minProducts[i - 1] * nums[i];
    const currMax = maxProducts[i - 1] * nums[i];
    // 将currMin和currMax与当前值对比，找出i位置的真正最大和最小值，存入数组
    minProducts[i] = Math.min(currMin, currMax, nums[i]);
    maxProducts[i] = Math.max(currMin, currMax, nums[i]);
    // 不断对比当前最大值，即可找出整个数组中的最大乘积
    max = Math.max(max, maxProducts[i]);
  }

  return max;
};

5. i的状态只与i - 1有关，maxProducts和minProducts可以简化为变量。

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxProduct = function (nums) {
  let max = nums[0];
  // 存储子数组的最大乘积，默认为第一项
  // 由于乘积可能会出现负负得正的情况，因此需要同时存储最大和最小值
  // 这样能避免只存储最大值，导致负值被抛弃的情况
  // 但实际上prevMin和prevMax都可能存在负值
  let prevMin = max;
  let prevMax = max;

  // 遍历数组，计算最大乘积
  for (let i = 1; i < nums.length; i++) {
    // 对于nums[i]来说，它一定会被计算到乘积中，但它之前已知的乘积是可以被抛弃的
    // 假设上一步的最大值和最小值需要使用，分别计算当前的最大和最小乘积
    const currMin = prevMin * nums[i];
    const currMax = prevMax * nums[i];

    // 将currMin和currMax与当前值对比，找出i位置的真正最大和最小值，存入数组
    prevMin = Math.min(currMin, currMax, nums[i]);
    prevMax = Math.max(currMin, currMax, nums[i]);

    // 不断对比当前最大值，即可找出整个数组中的最大乘积
    max = Math.max(max, prevMax);
  }

  return max;
};