乘积最大子数组

乘积最大子数组

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

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

题解：

如果我们用 dp (i) 开表示以第 i 个元素结尾的乘积最大子数组的乘积，a 表示输入参数 nums，那么根据「53. 最大子序和」的经验，我们很容易推导出这样的状态转移方程：

dp[i] = max(dp[i-1] * nums[i], nums[i])

得到如下的代码：

func maxProduct(nums []int) int {dp := make([]int, len(nums))dp[0] = nums[0]maxx := nums[0]for i:=1; i < len(nums); i++ {dp[i] = max(dp[i-1] * nums[i], nums[i])if maxx < dp[i] {maxx = dp[i]}}return maxx
}

但是，在这里，这样做是错误的。因为出现负数，负负得正会使得我们的最大值的子问题分解是错误的，解决方法呢是我们需要同时记录最小值，将最小值与当前元素的乘积放在比较选项之中

func maxProduct(nums []int) int {MAXX := make([]int, len(nums))MINN := make([]int, len(nums))MAXX[0], MINN[0] = nums[0], nums[0]maxx, minn := nums[0], nums[0]for i := 1; i < len(nums); i++ {MAXX[i] = max(nums[i], max(MAXX[i-1] * nums[i], MINN[i-1] * nums[i]))MINN[i] = min(nums[i], min(MINN[i-1] * nums[i], MAXX[i-1] * nums[i]))if maxx < MAXX[i] {maxx = MAXX[i]}if minn < MINN[i] {minn = MINN[i]}}return maxx
}