乘积最大子数组

解法:动态规划

思路

  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
}

评论(0)

评论