152. 乘积最大子序列

分析

这个题目和普通的一维DP, 二维DP都不一样.
不一样的地方, 它维护使用了两个角度的信息.

1. max_dp[i]
2. 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, 那么相当于以后的

1. max_dp[i] = {0}
2. 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