乘积为正数的最长连续子数组

[编程题]乘积为正数的最长连续子数组

热度指数：484 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一个长度为 n 的整数数组，请你找出其中最长的乘积为正数的子数组长度。

子数组的定义是原数组中一定长度的连续数字组成的数组。

数据范围： $1 \le n \le 10^5 \$ , 数组中的元素满足 $|val| \le 10^9 \$

示例1

输入

[1,2,3,-1,4]

输出

示例2

输入

[1,2,3,0,4]

输出

算法知识视频讲解

C++

Gandalf_Init

#include <vector>
class Solution {
    using ll=long long;
public:
    int findLongestSubArray(vector<int>& nums) {
       int len=(int)nums.size();
       vector<ll>fix(len);
       int ans=1;
       for(int i=0;i<len;i++)
       {
        if(nums[i]>0)nums[i]=1;
        else if(nums[i]<0)nums[i]=-1;
       }
       fix[0]=nums[0];
       int index=1;
       for(int i=1;i<len;++i)
       {
        fix[i]=fix[i-1]*nums[i];
        if(fix[i]>0)ans=max(index+1,ans);
        if(nums[i]!=0&&fix[i]==0)
        {
                fix[i]=nums[i];
                index=1;
                continue;
        }
        index++;
       }
       return ans;
    }

};

发表于 2023-12-12 22:21:42 回复(0)

小谷围做题家

package main

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param nums int整型一维数组 
 * @return int整型
*/
func findLongestSubArray( nums []int ) int {
    ans:=0
    var pre1,pre2,tmp int
    for _,x:=range nums{
        if x>0{
            pre1++
            if pre2!=0{
                pre2++
            }
        }else if x==0{
            pre1=0
            pre2=0
        }else{
            tmp=pre1
            if pre2==0{
                pre1=0
            }else{
                pre1=pre2+1
            }
            if tmp==0{
                pre2=1
            }else{
                pre2=tmp+1
            }
        }
        if pre1>ans{
            ans=pre1
        }
    }
    return ans
}

发表于 2023-03-15 16:27:10 回复(0)

进击的博仔

牛客调试力扣刷

发表于 2023-02-28 16:13:07 回复(0)

Java

菲尼克斯弗兰克

可以做一下最长有效的括号，类似的思路注意负数时需要补上之前的正数！

public class Solution {
    public int findLongestSubArray (List<Integer> nums) {
        int res = 0;
        int[] dp = new int[nums.size()];
        dp[0] = nums.get(0) > 0 ? 1 : 0;
        for (int i = 1; i < nums.size(); i++) {
            if (nums.get(i) > 0) { // 正数
                dp[i] = dp[i-1] + 1;
            } else if (nums.get(i) < 0) { // 负数
                int pre = i-dp[i-1]-1;
                if (pre >= 0 && nums.get(pre) < 0) { // 前推存在负数
                    dp[i] = dp[i-1] + 2;
                    if (pre-1 >= 0) { // 补上前面剩下的
                        dp[i] += dp[pre-1];
                    }
                }
            }
            res = Math.max(dp[i], res);
        }
        return res;
    }
}

发表于 2022-05-04 12:48:56 回复(0)

Java

_王泥煤

    public int findLongestSubArray (ArrayList<Integer> nums) {
        // write code here
        int[][] dp = new int[nums.size()][2];
        int ans = 0;
        if(nums.get(0) > 0) {
            dp[0][0] = 1;
            ans = 1;
        } else if(nums.get(0) < 0) {
            dp[0][1] = 1;
        }
        for(int i = 1; i < nums.size(); ++i) {
            if(nums.get(i) > 0) {
                dp[i][0] = dp[i-1][0] + 1;
                dp[i][1] = dp[i-1][1] == 0 ? 0 : dp[i-1][1] + 1;
            } else if(nums.get(i) < 0) {
                dp[i][0] = dp[i-1][1] == 0 ? 0 : dp[i-1][1] + 1;
                dp[i][1] = dp[i-1][0] + 1;
            } else {
                dp[i][0] = dp[i][1] = 0;
            }
            ans = Math.max(ans, dp[i][0]);
        }
        return ans;
    }

发表于 2022-03-03 01:28:40 回复(0)