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.

Example 3:

Input: nums = [-1,-2,-3,0,1]
Output: 2
Explanation: The longest subarray with positive product is [-1,-2] or [-2,-3].

Example 4:

Input: nums = [-1,2]
Output: 1

Example 5:

Input: nums = [1,2,3,5,-6,4,0,10]
Output: 4

Constraints:

• 1 <= nums.length <= 10^5
• -10^9 <= nums[i] <= 10^9

---

给一个数组，包含正数、负数和0，问最长连乘结果为正的长度是多少。

本题与LeetCode Maximum Product Subarray类似，要注意负负得正的情况。首先是传统DP好理解方法：设置dp_pos和dp_neg两个数组，分别表示遍历到i时，当前的最长连乘为正的长度和最长连乘为负的长度。则对于第i个位置，如果nums[i]是正数，则dp_pos直接+1；对于dp_neg，如果前一刻已经是连乘为负，即dp_neg[i-1]>0，则在前一刻基础上再乘以nums[i]还是负，所以负数长度可变长，即dp_neg+1；如果前一刻没有连乘为负，则增加一个正数也不会使连乘为负的长度增加，所以dp_neg=0。类似的可以讨论num[i]为负数的情况。如果nums[i]==0，则dp_pos和dp_neg都重置为0。

完整代码如下：

class Solution {
public:
    int getMaxLen(vector<int>& nums) {
        int n = nums.size();
        vector<int> dp_pos(n, 0), dp_neg(n, 0);
        if(nums[0] > 0) dp_pos[0] = 1;
        else if(nums[0] < 0) dp_neg[0] = 1;
        int ans = dp_pos[0];
        for(int i = 1; i < n; ++i) {
            if(nums[i] > 0) {
                dp_pos[i] = dp_pos[i - 1] + 1;
                dp_neg[i] = dp_neg[i - 1] > 0 ? dp_neg[i - 1] + 1 : 0;
            } else if(nums[i] < 0) {
                dp_pos[i] = dp_neg[i - 1] > 0 ? dp_neg[i - 1] + 1 : 0;
                dp_neg[i] = dp_pos[i - 1] + 1;
            }
            ans = max(ans, dp_pos[i]);
        }
        return ans;
    }
};

本代码提交AC，用时268MS。

因为DP只用到上一刻的状态，所以不用数组存储也可以，节省内存版本如下，不过需要注意tmp=pos_len保存上一刻的pos_len状态。

class Solution {
public:
    int getMaxLen(vector<int>& nums) {
        int n = nums.size();
        int pos_len = 0, neg_len = 0;
        if(nums[0] > 0) pos_len = 1;
        else if(nums[0] < 0) neg_len = 1;
        int ans = pos_len;
        for(int i = 1; i < n; ++i) {
            if(nums[i] > 0) {
                ++pos_len;
                neg_len = neg_len > 0 ? neg_len + 1 : 0;
            } else if(nums[i] < 0) {
                int tmp = pos_len;
                pos_len = neg_len > 0 ? neg_len + 1 : 0;
                neg_len = tmp + 1;
            } else if(nums[i] == 0) {
                pos_len = neg_len = 0;
            }
            ans = max(ans, pos_len);
        }
        return ans;
    }
};

本代码提交AC，用时368MS。