乘积为正数的最长子数组长度Java

文章发布较早，内容可能过时，阅读注意甄别。

# 题目

给你一个整数数组 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] 。

提示：

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

# 思路

状态机dp从二维到常量

# 解法


class Solution {
    public int getMaxLen(int[] nums) {
        int n = nums.length;
        // f[i][0]代表0-i位置的能获得到负数的子元素长度
        // f[i][1]代表0-i位置的能获得到正数的子元素长度
        var f = new int[n][2];
        if (nums[0] < 0) {
            f[0][0] = 1;
        }
        if (nums[0] > 0) {
            f[0][1] = 1;
        }
        int ans = f[0][1];
        for (int i = 1; i < n; i++) {
            //如果当前位i是正数，那么能得到正数的数量就是上一位(i-1)能获得正数的数量+1，能得到负数的数量就是上一位（i-1）能获得负数的数量+1。
            if (nums[i] > 0) {
                // 这边要做一个判断因为 如果当前位之前的全是正数，那么将无法得到负数，只有有负数的时候，当前位是正数你才能获得负数的结果
                if (f[i - 1][0] > 0)
                    f[i][0] = f[i - 1][0] + 1;
                f[i][1] = f[i - 1][1] + 1;
            }
            // 同上
            if (nums[i] < 0) {
                f[i][0] = f[i - 1][1] + 1;
                if (f[i - 1][0] > 0)
                    f[i][1] = f[i - 1][0] + 1;
            }
            ans = Math.max(f[i][1], ans);
        }
        return ans;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

# 总结

分析出几种情况，然后分别对各个情况实现

#Java