# 152. Maximum Product Subarray & 1567. Maximum Length of Subarray With Positive Product

 [**152. Maximum Product Subarray**](https://leetcode.com/problems/maximum-product-subarray/description/)

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.
```

***My Solutions:***

 和53题类似，但是加法累加结果只要是正的一定是递增，乘法中有可能现在看起来小的一个负数，后面跟另一个负数相乘就会得到最大的乘积。因此，需要在维护一个局部最大的同时，在维护一个局部最小，这样如果下一个元素遇到负数时，就有可能与这个最小相乘得到当前最大的乘积和

1\. 当遍历到一个正数时，此时的max等于之前的max乘以这个正数或者当前正数中的较大值，此时的min等于之前的min\*当前正数或者当前正数中的较小值。保证max和min的absolute value都是最大

2\. 当遍历到一个负数时，用一个变量temp保存之前的最大值max。max等于之前min乘以这个负数或者当前负数中的较大值，min等于之前保存的最大值temp\*当前负数或者当前负数中的较小值。

3\. 在每遍历完一个数时，都要更新最终的最大值。

```
class Solution {
    public int maxProduct(int[] nums) {
        if (nums == null || nums.length <= 0) return 0;
        
        // 这里全部初始化为第一个数
        int max = nums[0], min = nums[0], res = nums[0]; 
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] > 0) { 
                // 注意这里虽然此数是正数，还是要这样写。因为max/min有可能是0.
                max = Math.max(max * nums[i], nums[i]); 
                min = Math.min(min * nums[i], nums[i]);
            } else {
                int temp = max;
                max = Math.max(min * nums[i], nums[i]);
                min = Math.min(temp * nums[i], nums[i]);
            }
            res = Math.max(res, max);
        }
        return res;
    }
}
```

也可以写的很短

```
for (int i = 1; i < nums.length; i++) {
    int temp = max;
    max = Math.max(Math.max(max * nums[i], nums[i]), nums[i] * min);
    min = Math.min(Math.min(temp * nums[i], nums[i]), nums[i] * min);
    res = Math.max(res, max);
}    
```

**1567.Maximum Length of Subarray With Positive Product**

Given an array of integers `nums`, find the maximum length of a subarray where the product of all its elements is positive.

A subarray of an array is a consecutive sequence of zero or more values taken out of that array.

Return *the maximum length of a subarray with positive product*.

**Example 1:**

<pre><code><strong>Input: nums = [1,-2,-3,4]
</strong><strong>Output: 4
</strong><strong>Explanation: The array nums already has a positive product of 24.
</strong></code></pre>

**Example 2:**

<pre><code><strong>Input: nums = [0,1,-2,-3,-4]
</strong><strong>Output: 3
</strong><strong>Explanation: The longest subarray with positive product is [1,-2,-3] which has a product of 6.
</strong>Notice that we cannot include 0 in the subarray since that'll make the product 0 which is not positive.
</code></pre>

***My Solutions:***

这道题求长度，因此用变量pos储存结果一定为正数的长度，neg储存结果一定是负数的长度。

```
public int getMaxLen(int[] nums) {

    // pos means the local max length of subarray that can generate the biggest positive product result
    // neg means the local max length of subarray that can generate the smallest negative product result
    int pos = 0, neg = 0, maxLen = 0;
    for (int n : nums) {
        if (n == 0) { // reset numbers
            pos = 0;
            neg = 0;
        }
        else if (n > 0) {
            pos++;
            neg = neg == 0 ? 0 : neg + 1;
        } else {
            int temp = pos;
            pos = neg == 0 ? 0 : neg + 1;
            neg = temp + 1;
        }
        maxLen = Math.max(maxLen, pos);
    }
    return maxLen;
}
```