152. Maximum Product Subarray

# Medium

Key idea: Dynamic Programming

Harder than Maximum Subarray because of '-', so record the minimun subarray is necessary too.

Think it in a simper way, max and min can only one of nums[i], nums[i]*max and nums[i]*min

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        # edge case
        if len(nums) == 1:
            return nums[0]
        
        # regular case
        res = nums[0]
        mx = nums[0]
        mn = nums[0]
        
        for i in range(1, len(nums)):
            tmp_mx = mx
            tmp_mn = mn
            mx = max(max(nums[i], tmp_mx*nums[i]), tmp_mn*nums[i])
            mn = min(min(nums[i], tmp_mx*nums[i]), tmp_mn*nums[i])
            res = max(mx, res)
                
        return res