LC 0152 [M] Maximum Product Subarray - ALawliet/algorithms GitHub Wiki

similar to product of array except self trick

we need to track the min too because multiplying opposite signs makes it smaller

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        res = max(nums)
        curMin, curMax = 1, 1
        
        for n in nums:
            # not needed
            # if n == 0:
            #     curMin, curMax = 1, 1
            #     continue
            
            tmp = curMax * n
            curMax = max(n * curMax, n * curMin, n) # ++, --, -+
            curMin = min(tmp, n * curMin, n) # ++, --, -+
            res = max(res, curMax)
            
        return res

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        prefix, suffix, max_so_far = 0, 0, float('-inf')
        for i in range(len(nums)):
            prefix = (prefix or 1) * nums[i]
            suffix = (suffix or 1) * nums[~i] # ~i = -1-i = n-1-i
            max_so_far = max(max_so_far, prefix, suffix)
        return max_so_far

class Solution:
    def maxProduct(self, A):
            B = A[::-1]
            for i in range(1, len(A)):
                A[i] *= A[i - 1] or 1
                B[i] *= B[i - 1] or 1
            return max(A + B)