乘积为整数的最长子数组长度

1567. 乘积为正数的最长子数组长度

难度：中等

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

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

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

示例 1：

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

示例 2：

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

示例 3：

输入：nums = [-1,-2,-3,0,1]
输出：2
解释：乘积为正数的最长子数组是 [-1,-2] 或者 [-2,-3] 。

示例 4：

输入：nums = [-1,2]
输出：1

示例 5：

输入：nums = [1,2,3,5,-6,4,0,10]
输出：4

提示：

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

动态规划

• 当$nums[i]>0$时：

$positive[i] = positive[i-1]+1;$

$\text { negative[ } i]=\left{\begin{array}{ll}
\text { negative }[i-1]+1, & \text { negative }[i-1]>0 \
0, & \text { negative }[i-1]=0
\end{array}\right.$

• 当$nums[i]<0$时：

$negative[i]=positive[i-1]+1$

$\text { positive }[i]=\left{\begin{array}{ll}
\text { negative }[i-1]+1, & \text { negative }[i-1]>0 \
0, & \text { negative }[i-1]=0
\end{array}\right.$

• 当$nums[i]=0$时

  $positive[i]=0;$

  $negative[i]=0;$

class Solution {
    public int getMaxLen(int[] nums) {
        int n=nums.length;
        int []positive=new int [n];
        int []negative=new int [n];

        if(nums[0]>0)positive[0]=1;
        else if(nums[0]<0)negative[0]=1;
        int maxLength = positive[0];
        for(int i=1;i<nums.length;i++){
            if(nums[i]>0){
                positive[i] = positive[i-1]+1;
                negative[i] = negative[i - 1] > 0 ? negative[i - 1] + 1 : 0;
            }else if(nums[i]<0){
                negative[i] = positive[i-1]+1;
                positive[i] = negative[i-1]>0 ? negative[i-1]+1:0;
            }
            // else 0 全部清0
           maxLength = Math.max(positive[i],maxLength);
        }

        return maxLength;
    }
}

赏

谢谢你请我吃糖果

微信