85.LeetCode.152. 乘积最大子序列

• 标签： 数组 动态规划
• 难度： 中等

• 题目描述

• 我的解法

此题与LeetCode.53. 最大子序和 不同， 因为乘积值受到正负号的影响。 仍旧采用动态规划求解。 用 Max[i] 表示以 nums[i] 为结尾的最大子序列乘积值， Min[i] 表示以 nums[i] 为结尾的最小子序列乘积值。 不难推出递推公式为：

Max[i]=max(a[i], Max[i-1]*a[i], Min[i-1]*a[i])
Min[i]=min(a[i], Max[i-1]*a[i], Min[i-1]*a[i])

class Solution(object):
    def maxProduct(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        Ans = Min = Max = nums[0]
        for n in nums[1:]:
            temp = Max
            Max = max(Max * n, Min * n, n)
            Min = min(temp * n, Min * n, n)
            Ans = max(Max, Ans)
        return Ans
            

• 其他解法

暂略。