152. Maximum Product Subarray

Medium

Given an integer array nums, find the contiguous subarray within an array (containing at least one number) which has the largest product.

😇 Solution

O(n)

#Dynamic Programming - Memoization

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        
        memo = [0 for _ in range(len(nums))]
        memo[0] = nums[0]
        imax = imin = memo[0]
        
        for i in range(1,len(nums)):
            
            if nums[i] < 0:
                imax,imin = imin,imax
            
            imax = max(nums[i], nums[i]*imax)
            imin = min(nums[i], nums[i]*imin)
            
            memo[i] = max(memo[i-1],imax)
        
        return memo[-1]