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

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

热度指数：495 时间限制：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]

输出

算法知识视频讲解

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)