个人练习-Leetcode-1567. Maximum Length of Subarray With Positive Product

题目链接https://leetcode.cn/problems/maximum-length-of-subarray-with-positive-product/

题目大意：给出一个数组nums[]，求一个最长子串，要求其乘积为正数。

思路：首先要注意0的位置，因为如果一个子串中有0，那么乘积必然是0，无法为正数。那么实际上可以把nums按照0分割成若干非零子串来做，对这些非零子串再找最长的满足要求的子串。这个过程只需线性扫描一遍即可。

每次循环，让start为第一个非零元素下标，end为start后面的第一个0的位置，如果后面一直没有0，那么end == nums.size()，可以看作nums[]最后又添了一个0，效果相同。

于是start到end-1位置上的所有元素都是非零的，只需在这个范围内找满足条件的子串即可。在扫描时我们记录所有负数的位置到minus_pos[]中，那么这个子串长度为end-start，

• 如果负数的个数minus_pos.size()为偶数，那么整个子串就满足条件，长度不用变化；
• 如果负数个数为奇数，那么截止到最边缘的一个负数的子串满足条件，长度为end-start-min(end-minus_pos.back(), minus_pos[0]-start+1)，最边缘即离start或者end最近

一轮循环完后更新start和end，往复，直到end到nums[]的末尾为止。因为只扫描了一遍，时间复杂度为O(N)

while (end < nums.size()) {
        int len = 0;
        while (nums[start] == 0) start++;
        end = start;
        vector<int> minus_pos;
        while (end < nums.size() && nums[end] != 0) {
            if (nums[end] < 0)
                minus_pos.push_back(end);
            end++;
        }

        if (minus_pos.size() % 2) {
            len = (end - start) -
                  min(end-minus_pos.back(), minus_pos[0]-start+1);
        }
        else {
            len = end - start;
        }

        max_len = max(max_len, len);

        start = end+1;
        end = start;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

完整代码

class Solution {
public:
    int getMaxLen(vector<int>& nums) {
        int start = 0, end = 0;
        int max_len = 0;
        while (end < nums.size()) {
            int len = 0;
            while (nums[start] == 0) start++;
            end = start;
            vector<int> minus_pos;
            while (end < nums.size() && nums[end] != 0) {
                if (nums[end] < 0)
                    minus_pos.push_back(end);
                end++;
            }

            if (minus_pos.size() % 2) {
                len = (end - start) -
                    min(end-minus_pos.back(), minus_pos[0]-start+1);
            }
            else {
                len = end - start;
            }

            max_len = max(max_len, len);

            start = end+1;
            end = start;
        }

        return max_len;
    }
};
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