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

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

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:

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

Example 2:

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

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