> For the complete documentation index, see [llms.txt](https://joshualbarb.gitbook.io/leetcode-problems/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://joshualbarb.gitbook.io/leetcode-problems/array-math-1/maximum-product-subarray.md).

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

![](/files/-MM2X0oM5ag6M5xDeA0O)

## 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;