[数据结构与算法]152-乘积最大子数组

题目

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

示例 1:

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

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

题解 动态规划

var maxProduct = (nums) => {
  let res = nums[0]
  let prevMin = nums[0]
  let prevMax = nums[0]
  let temp1 = 0, temp2 = 0
  for (let i = 1; i < nums.length; i++) {//从1开始，0已经定义了
    temp1 = prevMin * nums[i]
    temp2 = prevMax * nums[i]
    prevMin = Math.min(temp1, temp2, nums[i])
    prevMax = Math.max(temp1, temp2, nums[i])
    res = Math.max(prevMax, res)
  }
  return res
}

笔记：

1.dp[i][x] 只和 dp[i - 1][x]有关，与再之前的结果无关
我们用两个变量分别去存每个位置算出的最小积和最大积，在迭代中更新即可

- base case
  prevMin = nums[0]
  prevMax = nums[0]
- 状态转移方程:
  prevMin = min( prevMin * nums[i], prevMax * nums[i], nums[i])  从第 0 项到第 i 项范围内的子数组的最小乘积
- prevMax = max( prevMin * nums[i], prevMax * nums[i], nums[i])  从第 0 项到第 i 项范围内的子数组的最大乘积

等号右边的 prevMin 和 prevMax 属于 dp[i - 1]的。等号左边的 prevMin 和 prevMax 属于 dp[i] 的
错误：第一个等式求出的新 prevMin 用在第二个等式的计算
解决：用变量暂存 prevMin * nums[i]和 prevMax * nums[i]

2. 三种可能，负值乘之前的最小值，正值*之前的最大值，本身