乘积最大子数组

• 算法与数据结构
• 2021-02-26 09:27:30

解法：动态规划

思路：

1. 遍历数组时计算当前最大值，不断更新。
2. 不要漏掉负负得正的情况

代码：

/**
 * @question 乘积最大子数组
 * @param {number[]} nums
 * @return {number}
 */
const maxProduct = (nums) => {
  let res = nums[0]
  let prevMin = nums[0]
  let prevMax = nums[0]
  let tempMin = 0, tempMax = 0
  for (let i = 1; i < nums.length; i++) {
    tempMin = prevMin * nums[i]
    tempMax = prevMax * nums[i]
    prevMin = Math.min(tempMax, tempMin, nums[i])
    prevMax = Math.max(tempMax, tempMin, nums[i]) // 此处容易忽略负负得正的情况
    res = Math.max(prevMax, res)
  }
  return res
}