Maximum Product Subarray

Array Math/Dynamic Programming

Problem

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

For example:

Input: [-2, 3, -4]
Output: 24
Explanation: [-2, 3, -4] has the largest 
product of 24

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

Thought Process

• We can apply dynamic programming to this problem. Remember for a problem to be classified as dynamic programming it must have: optimal substructure and overlapping problems

• At each index, we will record the local minimum and the local maximum

  • We need to record the local minimum for the case where we come across a negative element and need to multiply it by the largest negative number

  • For the case where the current element is negative, the local minimum will be between that current element or (current element x previous local maximum).

Solution

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        #need to store minimum number and max number    
        localMax = globalMax = localMin = nums[0]
        
        for i in range(1, len(nums)):
            prevMax = localMax
            if nums[i] > 0:
                localMax = max(nums[i], nums[i]*localMax)
                localMin = min(nums[i], nums[i]*localMin)
            elif nums[i] < 0:
                localMax = max(nums[i], localMin*nums[i])
                localMin = min(nums[i], nums[i] * prevMax)
            else:
                localMax = 0
                localMin = 0
            
            globalMax = max(globalMax, localMax)
        return globalMax  
        
        
        

Key Facts

• This is a DP problem where the optimal solution to the whole problem contains optimal solution to the subproblems

  • Here the optimal solution to subproblems is the local minimum

  • We are storing the local minimum and local maximum for each subproblem

• We need to record the local minimum because for the case when we come across a negative number, multiplying these two negative numbers together will result in a large positive number

Time Complexity

• Time: $O(n)$

• Space: $O(1)$