1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public int getMaxLen(int[] nums) {
        int lastZero = -1, firstNegative = -1, sum = 0, ans = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == 0) {
                lastZero = i;
                firstNegative = -1;
                sum = 0;
                continue;
            }
            if (nums[i] < 0) {
                firstNegative = firstNegative == -1 ? i : firstNegative;
                sum += 1;
            }
            if (sum % 2 == 0) {
                ans = Math.max(ans, i - lastZero);
            } else {
                ans = Math.max(ans, i - firstNegative);
            }
        }
        return ans;
    }
}

让每一个位置的元素都尝试成为subarray的最后一个元素, 那么看这样往左最多能延伸多少.

首先0不能作为subarray中的元素. 因为我们要求是subarray的元素相乘大于0. 其次如果我们要记录从上一个0到该元素为止(包括该元素), 一共遇到了多少个负数. 如果负数的个数是偶数个, 那么能够互相负负得正, 此时最长长度就是当前idx i减去上一个zero出现的位置即可(也就是不包含上一个zero但是包含此时的i). 如果目前遇到的负数个数是奇数个, 那么我们就需要移除上一个0到这个位置中第一个出现的negative及以前的数字.

我们可以认为0和该数组的边界把整个数组分割成了不同的部分. 每个部分能够形成自己的subarray, 不能横跨. 这样理解就好一些.

时间复杂度: O(n) 因为我们要遍历数组.
空间复杂度: O(1) 我们没有用额外的数据结构或者递归等等.