最大连续子序列乘积

152. 乘积最大子数组 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)

算法题：最大连续子序列乘积

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

示例 1:

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

示例 2:

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

题解：动态规划

定义$ f(i){max} $ 为 以第 i 个元素结尾的乘积最大子数组的乘积，$ f(i){min} $ 为以第 i 个元素结尾的乘积最小子数组的乘积，所以有

$f(i)_{max} = max\{f_{max}(i-1)*a_i,f_{min}(i-1)*a_i,a_i\}$

$f(i)_{min} = min\{f_{max}(i-1)*a_i),f_{min}(i-1)*a_i,a_i\}$

var maxProduct = function (nums) {
  const max = [nums[0]]
  const min = [nums[0]]
  let ans = nums[0]
  for (let i = 1;i<nums.length;i++) {
    let a = max[i - 1] * nums[i]
    let b = min[i - 1] * nums[i]
    max[i] = Math.max(a, nums[i], b)
    min[i] = Math.min(a, nums[i], b)
    ans = Math.max(max[i],ans)
  }
  return ans
};

在上面的代码中其实还可对max与min进行压缩，因为每次遍历只需要i-1的一个数据，之前的则可不用保存，所以可优化为：

var maxProduct = function (nums) {
  let max = num[0],min = nums[0], ans = nums[0]
  for (let i = 1;i<nums.length;i++) {
    let a = max * nums[i]
    let b = min * nums[i]
    max = Math.max(a, nums[i], b)
    min = Math.min(a, nums[i], b)
    ans = Math.max(max,ans)
  }
  return ans
};