LC 152

Solution to LeetCode 152 Maximum Product Subarray.

LeetCode 152

Maximum Product Subarray (Medium). [link]

To find the maximum product, we not only need to consider values as large (positive) as possible, we also need to consider negatives that can become large positive value after multiplying another negative. (negative * negative = positive. )

1] Bottom-up DP

ma[i] = max(ma[i-1] * nums[i], nums[i], mi[i-1] * nums[i])

mi[i] = min(ma[i-1] * nums[i], nums[i], mi[i-1] * nums[i])

dp[i] = max(dp[i-1], ma[i])

class Solution(object):
    def maxProduct(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        n = len(nums)
        if n <= 1: return [0,nums[0]][n]
        dp = max_dp = min_dp = nums[0]
        
        for i in range(1,n):
            max_dp, min_dp = max(max_dp * nums[i], nums[i], min_dp * nums[i]), min(max_dp * nums[i], nums[i], min_dp * nums[i])
            dp = max(dp, max_dp)
        return dp

2] Recursive DP

Time complexity = Space complexity = O(n)

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        @cache
        def dp(i):
            if i == 0: return nums[i], nums[i]
            mi, ma = dp(i-1)
            if nums[i] < 0:
                mi, ma = ma, mi
            return min(mi * nums[i], nums[i]), max(ma * nums[i], nums[i])
        return max(dp(i)[1] for i in range(len(nums)))