1567. Maximum Length of Subarray With Positive Product
Given an array of integers nums, find the maximum length of a subarray where the product of all its elements is positive.
A subarray of an array is a consecutive sequence of zero or more values taken out of that array.
Return the maximum length of a subarray with positive product.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| class Solution {
public:
int getMaxLen(vector<int>& nums) {
int res = 0, st = 0, negative = INT_MAX;
bool f = true;
for(int i = 0; i < nums.size(); i++) {
if(!nums[i]) {
f = negative = INT_MAX;
st = i + 1;
} else {
f = !((nums[i] > 0) ^ f);
if(!f) {
negative = min(negative, i);
res = max(res, i - negative);
} else {
res = max(res, i - st + 1);
}
}
}
return res;
}
};
|
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
| class Solution {
public:
int getMaxLen(vector<int>& nums) {
pair<int, int> t{0, INT_MIN}, f{INT_MAX, INT_MIN};
bool last = true;
int idx = 1;
int res = 0;
for(auto& num : nums) {
if(num == 0) {
if(idx == 1) continue;
last = true;
idx = 0;
res = max(res, max(t.second == INT_MIN ? 0 : t.second, f.first == INT_MAX ? 0 : f.second - f.first));
t = {0, INT_MIN}, f = {INT_MAX, INT_MIN};
} else {
if(last) {
if(num > 0) t.second = idx;
else f.second = idx, f.first = min(f.first, idx);
last = num > 0;
} else {
if(num < 0) t.second = idx;
else f.second = idx, f.first = min(f.first, idx);
last = num < 0;
}
}
idx++;
}
return idx != 1 ?
max(res, max(t.second == INT_MIN ? 0 : t.second, f.first == INT_MAX ? 0 : f.second - f.first)) : res;
}
};
|
