leetcode：152. 乘积最大子数组【考虑两个维度的dp】

分析

为了找到乘积最大的子数组
我们用当前能达到的最大值，最小值即可
具体的newmaxn = max(maxn * num, minn * minn, num)
newminn同理
因为可能是最小的负数乘当前的负数是最小
所以就不能简单地像子数组最大和这样解决
最后记录每个maxn的最大值即可

ac code

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        # 最大 + 最小子数组 => 乘积最大
        maxn, minn, ans = 1, 1, -inf
        for num in nums:
            # 保持连续
            maxn1, minn1 = max(maxn * num, minn * num, num), min(maxn * num, minn * num, num)
            maxn = maxn1
            minn = minn1
            ans = max(maxn, ans)
            #print(minn, maxn)
            
        return ans

总结

同时记录最大值和最小值的dp