152. Maximum Product Subarray

Information

  • Diffculty: Medium

  • Created: 2018-05-24 19:44:00

  • Last Motified: 2020-03-15 09:15:06

  • Tags: Array, Dynamic Programming

Intuition

This is a DP problem, for each node, we need to calculate the maximum and minimum product from the beginning.

Once there is a zero, all product must be reset to 1. Note that we shouldn’t update the value if the number is resetted or unchanged.

Solution

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        max_product = max(nums)
        pos = 0
        neg = 0
        for num in nums:
            if num == 0:
                pos = neg = 0
            elif num > 0:
                pos = max(pos * num, num)
                neg = num * neg
            elif num < 0:
                neg, pos = min(num * pos, num), neg * num
            if pos != 0:
                max_product = max(max_product, pos)
        return max_product