[NC]306. 乘积为正数的最长连续子数组

🚩传送门：牛客题目
力扣题目

题目

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

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

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

示例：

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

解题思路：动态规划

👉 定义：

• 其中 表示以第 个数做结尾，最长的正数序列长度
• 其中 表示以第 个数做结尾，最长的负数序列长度

那么我们不难发现，对于得到一个正负数序列，只有下面的方式

那么我们可以遍历数组的每个数字，对于每个数字分正负讨论

• 当前数字是正数

对于 正数序列 那么我们只需要知道的长度，在其基础上_+1_即可
对于 负数序列 那么我们只需要知道的长度，在其基础上_+1_即可

• 当前数字是负数

对于 负数序列 那么我们只需要知道的长度，在其基础上_+1_即可
对于 正数序列 那么我们只需要知道的长度，在其基础上_+1_即可

这样貌似可以了，真的吗？
如果当前数字是正数，但是的长度为怎么办，无论如何都构建不出以第 个数做结尾的负数序列，这时候只能
同理
如果当前数字是负数，但是的长度为怎么办，无论如何都构建不出以第 个数做结尾的正数序列，这时候只能

那么加上前序列是否为零就可以了吗？
如果当前数字是零值，无论的长度是多少

• 无论如何都构建不出以第 个数做结尾的负数序列，这时候只能
• 无论如何都构建不出以第 个数做结尾的正数序列，这时候只能

复杂度分析

时间复杂度： ，其中 是数组的长度，只需要遍历数组一次。

空间复杂度： ，即为存储 所有状态使用的空间。

我的代码

public class Solution {
    public int findLongestSubArray (ArrayList<Integer> nums) {
        int[][]dp=new int[nums.size()][2]; 
        if(nums.get(0)>0)dp[0][0]=1;
        else if(nums.get(0)<0)dp[0][1]=1;
        else ;
        int res=0;
        for(int i=1;i<nums.size();i++){
            if(nums.get(i)>0){
                // 正数=当前正数*前面正数 ,因此长度是在前面正数序列的长度上+1
                dp[i][0]=Math.max(dp[i-1][0]+1,dp[i][0]);
                // 负数=当前正数*前面负数,因此长度是在前面负数序列的长度上+1
                if(dp[i-1][1]==0){    // 特殊情况:当前正数,但上一个负数序列长度为0,无法构成负数序列
                    dp[i][1]=0;  
                }else dp[i][1]=Math.max(dp[i-1][1]+1,dp[i][1]);
            }else if(nums.get(i)<0){
                // 负数=当前负数*前面正数,因此长度是在前面正数序列的长度上+1
                dp[i][1]=Math.max(dp[i-1][0]+1,dp[i][1]);
                // 正数=当前负数*前面负数,因此长度是在前面负数序列的长度上+1
                if(dp[i-1][1]==0){    // 特殊情况:当前负数,但上一个正数序列长度为0,无法构成正数序列
                    dp[i][0]=0;
                }else dp[i][0]=Math.max(dp[i-1][1]+1,dp[i][0]);
            }else{
                // 0 , 0乘以任何数都是0
                dp[i][0]=0;
                dp[i][1]=0;
            }
            res=Math.max(res,dp[i][0]);
        }
        return res;
    }
}

我们不难发现的状态只和有关，因此我们可以使用dp_pre_0和dp_pre_1来保存前者的状态

复杂度分析

时间复杂度： ，其中 是数组的长度，只需要遍历数组一次。

空间复杂度： ，常数空间。

优化代码

public class Solution {
    public int findLongestSubArray (ArrayList<Integer> nums) {
        int[][]dp=new int[nums.size()][2]; 
        int dp_pre_0=0;  // 保存前项正数序列长度
        int dp_pre_1=0;  // 保存前向负数序列长度
        int dp_cur_0=0;  // 保存当前正数序列长度
        int dp_cur_1=0;  // 保存当前负数序列长度
        if(nums.get(0)>0)dp_pre_0=1;
        else if(nums.get(0)<0)dp_pre_1=1;
        else ;
        int res=0;
        for(int i=1;i<nums.size();i++){
            if(nums.get(i)>0){
                // 正数序列=当前正数*前面正数序列,因此长度是在前面正数序列的长度上+1
                dp_cur_0=dp_pre_0+1;
                // 负数序列=当前正数*前面负数序列,因此长度是在前面负数序列的长度上+1
                if(dp_pre_1==0){    // 特殊情况:上一个负数序列长度为0,当前是正数,故无法构成负数序列
                    dp_cur_1=0;  
                }else dp_cur_1=dp_pre_1+1;
            }else if(nums.get(i)<0){
                // 负数序列=当前负数*前面正数序列,因此长度是在前面正数序列的长度上+1
                dp_cur_1=dp_pre_0+1;
                // 正数序列=当前负数*前面负数序列,因此长度是在前面负数序列的长度上+1
                if(dp_pre_1==0){    // 特殊情况:上一个正数序列长度为0,当前是负数,故无法构成负数序列
                    dp_cur_0=0;
                }else dp_cur_0=dp_pre_1+1;
            }else{
                // 当前数为0 , 0乘以任何数都是0
                dp_cur_0=0;
                dp_cur_1=0;
            }
            res=Math.max(res,dp_cur_0);
            dp_pre_0=dp_cur_0;    
            dp_pre_1=dp_cur_1;    
        }
        return res;
    }
}