分析
这个题目和普通的一维DP, 二维DP都不一样.
不一样的地方, 它维护使用了两个角度的信息.
- max_dp[i]
- min_dp[i]
注意这个题目中0的作用很重要.
for i in range(1,n):
t_max = max_dp[i-1]*nums[i]
t_min = min_dp[i-1]*nums[i]
max_dp[i] = max(t_max, t_min, nums[i])
min_dp[i] = min(t_max, t_min, nums[i])
max_ret = max(max_ret, max_dp[i])
注意代码, 一旦出现了0, 也就是nums[i]==0, 那么相当于以后的
- max_dp[i] = {0}
- min_dp[i]={0}
DP 状态
class Solution(object):
def maxProduct(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
n = len(nums)
# max_dp[i]表示前i个数字, 包括i本身, 最大乘积
max_dp = [0]*n
# min_dp[i] 表示前i个数字,包括i本身, 最小的乘积
min_dp = [0]*n
# 初始化,最起码有一个结果
max_dp[0] = nums[0]
min_dp[0] = nums[0]
max_ret = nums[0]
for i in range(1,n):
t_max = max_dp[i-1]*nums[i]
t_min = min_dp[i-1]*nums[i]
max_dp[i] = max(t_max, t_min, nums[i])
min_dp[i] = min(t_max, t_min, nums[i])
max_ret = max(max_ret, max_dp[i])
return max_ret
