题目描述

给你一个整数数组 nums ，请你求出乘积为正数的最长子数组的长度。

一个数组的子数组是由原数组中零个或者更多个连续数字组成的数组。

请你返回乘积为正数的最长子数组长度。

样例

输入：nums = [1,-2,-3,4]
输出：4
解释：数组本身乘积就是正数，值为 24 。

输入：nums = [0,1,-2,-3,-4]
输出：3
解释：最长乘积为正数的子数组为 [1,-2,-3] ，乘积为 6 。
注意，我们不能把 0 也包括到子数组中，因为这样乘积为 0 ，不是正数。

算法1

(动态规划) $O(N)$

 1 -2 -3 4

+: 0 1 0 3 4
-: 0 0 2 1 2
维护两个数组，表示以该数字结尾的乘积为正负的最长状态．根据arr[i]的正负以及０来判断此时的状态．

时间复杂度

$O(N)$

参考文献

C++ 代码

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