# Maximum Product Subarray

## Problem

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

{% hint style="info" %}
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.
```

{% endhint %}

### 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). 

![](https://1063826111-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MGdx41c9p2PMgIHbUTK%2F-MM2StBgXYs3bsZzTSgP%2F-MM2X0oM5ag6M5xDeA0O%2FIMG_BCB32026BF1B-1.jpeg?alt=media\&token=b7935202-5fbd-4a23-b2a6-4de3eb717511)

## 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)$$&#x20;
* **Space:** $$O(1)$$&#x20;