乘积最大子数组-152

[sl1673495]

给你一个整数数组 nums ，请你找出数组中乘积最大的连续子数组（该子数组中至少包含一个数字）。

示例 1:

输入: [2,3,-2,4]
输出: 6
解释:  子数组 [2,3] 有最大乘积 6。
示例 2:

输入: [-2,0,-1]
输出: 0
解释:  结果不能为 2, 因为 [-2,-1] 不是子数组。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/maximum-product-subarray
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

这题和 53. 最大子序和 的思路是类似的，都是从后往前来通过动态规划划分子数组。

对于每一个下标的规划，分别有两种选择：

1. 只拿当前值。
2. 拿当前值，并且乘上后续项的最值。

比如对于 [2, -1]，来说，从后往前规划，dp[1] 后面没有值了，所以只能选择 -1，而 dp[0] 则可以选择只取 2（构成子数组 [2]），也可以选择 2 * -1（构成子数组 [2, -1]），显然前者比较大，因此 dp[0] = 2。

这题比较特殊的是，后面的最小值（负数）也有可能和前面的负数凑成最大值。比如[-2, 2, -3]，其实他们的最大值是三个数的乘积，而如果单纯的判断大小的话，到 dp[1]也就是以 2 为起点的位置，就会选择把 2 保留，而把 2 * -3 = -6 丢弃掉了。但这样会导致前面的-2 没办法和 -6 相乘，得到真正的最大值 12。

所以我选择在每次 dp 填表的时候，会去从「只选择当前值」和「选择当前值 * 后一项开始的最大值」和「选择当前值 * 后一项开始的最小值」找出最大和最小值，分别记录下来。这样即使是负数乘负数（负数会被记录为最小值）的情况也可以 cover 到了。

运行到最后，只需要在 dp 数组中挑出所有值中的最大值即可。这是因为子数组的起点是不固定的。

题解

let maxProduct = function (nums) {
  let dp = [];
  let n = nums.length;

  let last = nums[n - 1];
  dp[n - 1] = {
    max: last,
    min: last,
  };

  for (i = nums.length - 2; i >= 0; i--) {
    let num = nums[i];
    let withNextMin = num * dp[i + 1].min;
    let withNextMax = num * dp[i + 1].max;
    let withoutNext = num;
    dp[i] = {
      max: Math.max(withoutNext, withNextMin, withNextMax),
      min: Math.min(withoutNext, withNextMin, withNextMax),
    };
  }

  return Math.max(...dp.map(({ max }) => max));
};

maxProduct([2, 3, -2, 4]);

优化解

空间复杂度优化为 O(1)，在运行的过程中不断去记录上一个最大最小值以及全局最大最小值即可。

let maxProduct = function (nums) {
    let n = nums.length

    let last = nums[n - 1]

    let prevMax = last
    let prevMin = last
    let allMax = last
    let allMin = last

    for (i = nums.length - 2; i >= 0; i--) {
        let num = nums[i]
        let withNextMin = (num * prevMin)
        let withNextMax = (num * prevMax)
        let withoutNext = num

        prevMax = Math.max(withoutNext, withNextMin, withNextMax)
        prevMin = Math.min(withoutNext, withNextMin, withNextMax)

        allMax = Math.max(allMax, prevMax)
        allMin = Math.min(allMin, prevMin)
    }

    return allMax
};