Leetcode 152. Maximum Product Subarray (Python)

Related Topic

Dynamic-Programming.

Description

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

Sample I/O

Example 1

Input: [2,3,-2,4]
Output: 6
Explanation: [2,3] has the largest product 6.

Example 2

Input: [-2,0,-1]
Output: 0
Explanation: The result cannot be 2, because [-2,-1] is not a subarray.

Methodology

This question solved by Dynamic Programming. It is similar with question 53. Maximum Subarray .

Basic idea

We need to track both maxmium product of subarray and minimum product of subarray. The reason of tracking minimun product of subarray is if there are even amount of negative numbers, then there is possiblility that the last negative number multiple previous product of subarray (which ic negative) can be the maximum product of subarray.

Conditions

There are two conditions need to consider:

1. If all number are positive, the maximum product of subarray is product of all subarray.

2. If not all numbers are positive, then we need to consider the previous product and current number, since we keep tracking the both maximum and minimum product of subarray, so each time you have two selection of product for the current number:

   1. If current number is positive, then the current maximum product of subarray is always max(max(max_product, min_product) x number, number) = max(max_product, min_product) x number = current_max_product and the minimum product of subarray is always min(min(max_product, min_product) x number, number) = number = current_min_product.

   2. If current number is negative, then the current maximum product of subarray should be max(min(max_product, min_product) x number, number) = current_max_product and the current minimum product of subarray is min(max(max_product, min_product) x number, number) = current_min_product.

From above, the only hard part for this question is to find the pattern when current number is negative. This is a classic dynamic question, the previous cell is the min_product and max_product of previous subarray.

Code 1 (classic dynamic programming way)

def maxProduct(self, nums: List[int]) -> int:
        if min(nums)>0:return reduce(lambda x, y: x*y, nums)
        size = len(nums)
        dp = [[1,1]]*size
        dp[0]=[nums[0],nums[0]]#dp[0][0] indicate max and dp[0][1] indicate min
        for i in range(1, size):
            if nums[i]==0:
                dp[i]=[0,0]
            elif nums[i]>=0:
                cur_max = max(max(dp[i-1])*nums[i], nums[i])
                cur_min = min(min(dp[i-1])*nums[i], nums[i])
                dp[i]=[cur_max, cur_min]
            else:
                cur_max = max(min(dp[i-1])*nums[i], nums[i])
                cur_min = min(max(dp[i-1])*nums[i], nums[i])
                dp[i]=[cur_max, cur_min]
        return max([x[0] for x in dp])

Code 2 (optimazed dynamic programming way by using pointers)

def maxProduct(self, nums: List[int]) -> int:
        if min(nums)>0:
            return reduce(lambda x, y: x*y, nums)
        if not nums:
            return 
        locMin = locMax = gloMax = nums[0]
        for i in range(1,len(nums)):
            if nums[i]<0:
                temp = locMax
                locMax = max(locMin*nums[i], nums[i])
                locMin = min(temp*nums[i], nums[i])
            else:
                locMax=max(locMax*nums[i], nums[i])
                locMin=min(locMin*nums[i], nums[i])
            print(locMax, locMin)
            gloMax=max(gloMax, locMax)
        return gloMax

BigO

When iterate the whole list, the BigO is O(n) where n is size of the list. Each element will need to compare to previous pair, this give us O(1), in total O(n+1) which is O(n)