3511. Make a Positive Array
You are given an array nums. An array is considered positive if the sum of all numbers in each subarray with more than two elements is positive.
You can perform the following operation any number of times:
- Replace one element in
nums with any integer between -1018 and 1018.
Find the minimum number of operations needed to make nums positive.
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 makeArrayPositive(vector<int>& A) {
int res = 0, n = A.size(), i = 0;
while(i + 2 < n) {
vector<long long> pre{0};
long long best = 0;
while(i < n) {
pre.push_back(pre.back() + A[i++]);
if(pre.size() >= 4) {
best = max(best, pre[pre.size() - 4]);
if(pre.back() - best <= 0) {
res++;
break;
}
}
}
}
return res;
}
};
|
