leetcode：152. Product maximum subarray [consider DP of two dimensions]

analysis

To find the subarray with the largest product
We use the maximum value that can be reached at present , The minimum value is enough
Concrete newmaxn = max(maxn * num, minn * minn, num)
newminn Empathy
Because it may be the smallest negative number multiplied by the current negative number is the smallest
So we can't simply solve it like the maximal sum of subarrays
Last record each maxn The maximum value of

ac code

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        #  Maximum  +  The smallest array  =>  Product maximum 
        maxn, minn, ans = 1, 1, -inf
        for num in nums:
            #  Keep going 
            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

summary

Record the maximum and minimum values at the same time dp