152. 乘积最大子数组

mid

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

测试用例的答案是一个 32-位 整数。

子数组 是数组的连续子序列。

示例 1:

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

示例 2:

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

DP

非常神奇的一道题目

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
func maxProduct(nums []int) int {
	maxRes, minRes, res := nums[0], nums[0], nums[0]
	for i := 1; i < len(nums); i++ {
		maxTmp, minTmp := maxRes, minRes
		maxRes = max(maxTmp*nums[i], max(minTmp*nums[i], nums[i]))
		minRes = min(minTmp*nums[i], min(maxTmp*nums[i], nums[i]))
		res := max(maxRes, res)
	}
	return res
}

func max(a, b int) int {
	if a > b {
		return a
	} else {
		return b
	}
}

func min(a, b int) int {
	if a < b {
		return a
	} else {
		return b
	}
}