152_Maximum Product Subarray

Level: medium

Tag: array, dynamic programming

Question

Find the contiguous subarray within an array (containing at least one number) which has the largest product.

Example 1

Input: nums = [2,3,-2,4]
Output: 6

Example 2

Input: nums = [2,3,-2,4,-2]
Output: 96

Idea (dynamic programing)

Two steps to solve this problem:

• Suppose we've solved the problem for nums[1 .. i - 1], how can we extend that to nums[1 .. i]? maxProduct(nums[1 .. i]) is either maxProduct(nums[1 .. i-1]) (which we call Max), or it is maximum product of a subvector that ends in position i (which we call curMax).

• What's the maximum product of a subvector that ends in position i? Three possibilities:

  • just i itself

  • i * curMax, where curMax records the maximum with element 0, ..., i-1

  • i * curMin, where curMin records the minimum with element 0, ... , i-1. Because negative curMin may be the next curMax when i is negative.

Complexity

• Time: $O(n)$

• Space: $O(1)$

Solution

class Solution(object):
    def maxProduct(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if len(nums) == 0:
            return 0

        Max = curMax = curMin = nums[0]

        # dynamic programming
        for i in nums[1:]:
            # consider elemet i, compute the curMax and curMin
            curMax, curMin = max(i, i*curMax, i*curMin), min(i, i*curMax, i*curMin)
            # maxProduct(nums[1:i+1]) is the max of maxProduct(nums[1:i]) and curMax(nums[1:i+1])
            Max = max(Max, curMax)
        return Max