# 152. Maximum Product Subarray

## Description

<https://leetcode.com/problems/maximum-product-subarray/>

Note: the input array is assumed to have at least one element.

## Solution

This is similar to the [maximum subarray problem](https://monica-granbois.gitbook.io/cs-theory-and-problems/problems/leetcode/53.-maximum-subarray), which can be solved using Kadane's Algorithm. We can use what we learned from that problem and apply it here.

Because this question asks for the product, negative numbers have a different effect. A subarray may flip in and out of the solution as negative numbers are included.&#x20;

As with the maximum sum subarray, we will keep track of the current and max product. But we will need to keep track of the minimum product too. This is because a negative product may become positive if we encounter another negative number.

### Examples

Given an input of: \[5, 3, -1, 2, -2, -3, 6]

<table><thead><tr><th width="150">element</th><th>current product &#x26; sub array</th><th>current min product &#x26; sub array</th><th>max product &#x26; sub array</th></tr></thead><tbody><tr><td>5 </td><td><p>5  </p><p>[5]</p></td><td><p>5 </p><p>[5]</p></td><td><p>5 </p><p>[5]</p></td></tr><tr><td>3</td><td><p>15  </p><p>[5,3]</p></td><td><p>3 </p><p>[3]</p></td><td><p>15 </p><p>[5,3]</p></td></tr><tr><td>-1</td><td><p>-1 </p><p>[-1]</p></td><td><p>-15 </p><p>[5,3,-1]</p></td><td><p>15 </p><p>[5,3]</p></td></tr><tr><td>2</td><td>2 [2]</td><td><p>-30 </p><p>[5,3,-1,2]</p></td><td><p>15 </p><p>[5,3]</p></td></tr><tr><td>-2</td><td><p>60 </p><p>[5, 3, -1, 2, -2]</p></td><td><p>-4 </p><p>[2, -2]</p></td><td><p>60 </p><p>[5, 3, -1, 2, -2]</p></td></tr><tr><td>-3</td><td><p>12 </p><p>[2, -2, -3]</p></td><td><p>-180 </p><p>[5, 3, -1, 2, -2, -3]</p></td><td><p>60 </p><p>[5, 3, -1, 2, -2] </p></td></tr><tr><td>6</td><td><p>72 </p><p>[2, -2, -3, -6]</p></td><td><p>-1080 </p><p>[5, 3, -1, 2, -2, -3, 6]</p></td><td><p>72</p><p>[2, -2, -3, -6]</p></td></tr></tbody></table>

Given an input of \[3, 2, 0, 5, 6, -1]

<table><thead><tr><th width="150">element</th><th>current product &#x26; sub array</th><th>current min product &#x26; sub array</th><th>max product &#x26; sub array</th></tr></thead><tbody><tr><td>3</td><td><p>3 </p><p>[3]</p></td><td><p>3</p><p>[3]</p></td><td><p>3</p><p>[3] </p></td></tr><tr><td>2</td><td><p>6</p><p>[3, 2]</p></td><td><p>2</p><p>[2]</p></td><td><p>6</p><p>[3,2]</p></td></tr><tr><td>0</td><td><p>0</p><p>[0]</p></td><td><p>0</p><p>[0]</p></td><td><p>6</p><p>[3,2]</p></td></tr><tr><td>5</td><td><p>5</p><p>[5]</p></td><td><p>0</p><p>[0, 5]</p></td><td><p>6</p><p>[3,2]</p></td></tr><tr><td>6</td><td><p>30</p><p>[5,6]</p></td><td><p>0</p><p>[0, 5, 6]</p></td><td><p>30</p><p>[5,6]</p></td></tr><tr><td>-1</td><td><p>0</p><p>[0, 5, 6, -1]</p></td><td><p>-30</p><p>[5, 6, -1]</p></td><td><p>30</p><p>[5, 6]</p></td></tr></tbody></table>

```python
class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        # since nums is guaranteed to be not empty, initialize the variables to the first element
        current_product = nums[0]
        max_product = nums[0]
        min_product = nums[0]
        for i in range(1, len(nums)):
            # The current_product is calculated at line 13. However, we need to use the current_product in the min_product calculation.
            # So we need to store the prev_current_product so that value can be used in the min_product calculation
            prev_current_product = current_product
            # This is like Kadane's algorithm where we take the max of either the current_product * the element, or the element. 
            # But now that we have a min_product as well, that value needs to be included too.
            current_product = max(min_product * nums[i], current_product * nums[i], nums[i])
            # Use Kadane like algorithm for the min_product too. Notice we are using the prev_current_product and not the current_product just
            # calculated above.
            min_product = min(min_product * nums[i], prev_current_product * nums[i], nums[i])
            max_product = max(max_product, current_product)
        return max_product
```