152.乘积最大子数组
152.乘积最大子数组
题解
题目：求子数组的乘积最大值
思路：
1.既然是连续子数组，那么这次答案与上一次有关（dpMax[i-1]*cnt） 2.而cnt可能是负数，所以这次答案与cnt也有关 3.而负负得正，可能变成最大值 4.所以dpMax[i] = max(cnt, dpMax[i-1]*cnt, dpMin[i-1]*cnt) 5.至于cnt=0的情况，dpMax直接为0了，只需要在ans中记录最大值即可 注意：不仅需要递推dpMax，dpMin也需要递推，为负负得正做准备 所以dpMin想要的值是最小值 dpMin[i] = min(cnt, dpMin[i-1]*cnt, dpMax[i-1]*cnt)
dpMax[i] = max(cnt, dpMax[i-1]*cnt, dpMin[i-1]*cnt) dpMin[i] = min(cnt, dpMin[i-1]*cnt, dpMax[i-1]*cnt)
代码
func maxProduct(nums []int) int { n := len(nums) if n == 1 { return nums[0] } dpMax := make([]int, n+1) dpMin := make([]int, n+1) ans := 0 for i := 1; i <= n; i++ { cnt := nums[i-1] dpMax[i] = max(max(cnt, dpMax[i-1]*cnt), dpMin[i-1]*cnt) dpMin[i] = min(min(cnt, dpMin[i-1]*cnt), dpMax[i-1]*cnt) ans = max(ans, dpMax[i]) } return ans } func max(i, j int) int { if i > j { return i } return j } func min(i, j int) int { if i > j { return j } return i }
func maxProduct(nums []int) int { n := len(nums) dpMax, dpMin, ans := nums[0], nums[0], nums[0] for i := 1; i < n; i++ { cnt := nums[i] mx, mn := dpMax, dpMin dpMax = max(mx*cnt, max(cnt, mn*cnt)) dpMin = min(mn*cnt, min(cnt, mx*cnt)) ans = max(ans, dpMax) } return ans } func max(i, j int) int { if i > j { return i } return j } func min(i, j int) int { if i > j { return j } return i }
