// 1D DP, 正负分类; 时间O(n), 空间O(1): 滚动数组优化
func maxProduct(nums []int) int {
n := len(nums)
fmax, fmin, ans := nums[0], nums[0], nums[0]
for i := 1; i < n; i++ {
mx, mn := fmax, fmin
fmax = max(mx * nums[i], max(mn * nums[i], nums[i]))
fmin = min(mx * nums[i], min(mn * nums[i], nums[i]))
ans = max(fmax, ans)
}
return ans
}
func max(x, y int) int {
if x > y {
return x
}
return y
}
func min(x, y int) int {
if x < y {
return x
}
return y
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24