# Maximum Product Subarray

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

**Example 1:**

```
Input:
 [2,3,-2,4]

Output:
6
Explanation:
 [2,3] has the largest product = 6.
```

**Example 2:**

```
Input:
 [-2,0,-1]

Output:
 0

Explanation:
 The result cannot be 2, because [-2,-1] is not a subarray.
```

分析

2个负数相乘可以得到最大值，需要存储当前最小的数。

```
*  second method: DP: curMax is the max of product contains the current element;
 *        since element can be negetive, maximum value can be obtain by product of two negtive numbers;
 *        we also need to store the current minimum product;
 *        when go to next element;
 *        if nums[i] < 0; curMax = Math.max(nums[i], nums[i]* curMin);
 *                        curMin = Math.min(nums[i], nums[i]* curMax);
 *                        (can swap curMax and curMin, and conbine the expression for those two conditions.
 *        else:           curMax = Math.max(nums[i], nums[i]* curMax);
 *                        curMin = Math.min(nums[i], nums[i]* curMin);
```

可以直接交换curMin和curMax

当前状态需要考虑前面的几步，而无法从前一个数直接决定：比如前面数可能取了负数成了最小，但遇到下一个负数成了最大，所以前数需要保留负数态。如果只考虑一个状态，前数会直接取正数，导致得不到最大。

所以这里设置两个全局变量以便考虑前面几个的状态，同时注意curMax和curMin都必须包含当前数，意味着下一步使用这俩变量时候，保证了数组的连续性。

答案

```
public class Solution {
    /**
     * @param nums: An array of integers
     * @return: An integer
     */
    public int maxProduct(int[] nums) {
        // write your code here

        if(nums == null || nums.length == 0) {
            return 0;
        }
        int n = nums.length;

        int max = nums[0], curMin = nums[0], curMax = nums[0];
        for(int i = 1; i < n; i ++){
            if(nums[i] < 0) {
            int temp = curMax;
               curMax = curMin;
               curMin = temp;
            } 
            curMax = Math.max(curMax * nums[i], nums[i]);
            curMin = Math.min(curMin * nums[i], nums[i]);
            max = Math.max(max, curMax);
        }

        return max;

    }
}
```

python

负负得正，所以2个数组，一个存最大一个存最小

```
class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        n = len(nums)
        dp = [1] + [i for i in nums]
        mdp = [1] + [i for i in nums]
        res = float('-inf')
        for i in range(1,n+1):
            dp[i] = max(dp[i],dp[i-1]*nums[i-1],mdp[i-1]*nums[i-1])
            mdp[i] = min(mdp[i],mdp[i-1]*nums[i-1],dp[i-1]*nums[i-1])
            res = max(res,dp[i])
        return res
```

因为只和前面状态min,max相关，并且当前态就能比较出res，只要设置这3个变量即可

```
class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        
        mn,mx,res = 1,1,float('-inf')
        for i in nums:
            mn,mx = min(i, mn*i,mx*i),max(i,mx*i,mn*i)
            res = max(mn,mx,res)
        return res
```


---

# 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://nataliekung.gitbook.io/ladder_code/l4dong-tai-gui-hua/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.