乘积最大子数组

Tips

相关题目:

• 53. 最大子序和

题目

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

示例

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

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

题解

这题是求数组中子区间的最大乘积, 对于乘法, 我们需要注意, 负数乘以负数, 会变成正数, 所以解这题的时候我们需要维护两个变量, 当前的最大值, 以及最小值, 最小值可能为负数, 但没准下一步乘以一个负数, 当前的最大值就变成最小值, 而最小值则变成最大值了.

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxProduct = function (nums) {
  let max = -Infinity
  let _max = 1 // 当前的最大值
  let _min = 1 // 当前的最小值

  for (const num of nums) {
    if (num < 0) {
      const temp = _max
      _max = _min
      _min = temp
    }

    _max = Math.max(_max * num, num)
    _min = Math.min(_min * num, num)

    max = Math.max(max, _max)
  }

  return max
}