152. 乘积最大子数组(Medium)
# 题解
视频题解:https://www.bilibili.com/video/BV1wA411b7qZ?p=26
# Python示例
class Solution:
def maxProduct(self, nums: List[int]) -> int:
if not nums: return 0
minProductDp = [0] * len(nums)
maxProductDp = [0] * len(nums)
minProductDp[0] = maxProductDp[0] = ans = nums[0]
for i in range(1, len(nums)):
minProductDp[i] = min(nums[i],
nums[i] * minProductDp[i - 1],
nums[i] * maxProductDp[i - 1])
maxProductDp[i] = max(nums[i],
nums[i] * minProductDp[i - 1],
nums[i] * maxProductDp[i - 1])
ans = max(ans, maxProductDp[i], minProductDp[i])
return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
func max(nums ...int) int{
ans := nums[0]
for i:= 1; i < len(nums); i++ {
if nums[i] > ans {
ans = nums[i]
}
}
return ans
}
func min(nums ...int) int{
ans := nums[0]
for i:= 1; i < len(nums); i++ {
if nums[i] < ans {
ans = nums[i]
}
}
return ans
}
func maxProduct(nums []int) int {
if len(nums) == 0 {
return 0
}
if len(nums) == 1 {
return nums[0]
}
maxProductMemo := make([]int, len(nums))
minProductMemo := make([]int, len(nums))
maxProductMemo[0] = nums[0]
minProductMemo[0] = nums[0]
for i:= 1; i < len(nums); i++ {
maxProductMemo[i] = max(nums[i],
maxProductMemo[i - 1] * nums[i],
minProductMemo[i - 1] * nums[i])
minProductMemo[i] = min(nums[i],
maxProductMemo[i - 1] * nums[i],
minProductMemo[i - 1] * nums[i])
}
return max(maxProductMemo...)
}
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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
编辑 (opens new window)
上次更新: 2022/10/25, 02:40:54