# 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](/cs-theory-and-problems/problems/leetcode/53.-maximum-subarray.md), 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
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://monica-granbois.gitbook.io/cs-theory-and-problems/problems/leetcode/152.-maximum-product-subarray.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.