main.cpp (1654B)
1 #include <iostream> 2 #include <vector> 3 #include <unordered_set> 4 #include <unordered_map> 5 #include <algorithm> 6 #include <queue> 7 8 #define ll long long 9 10 using namespace std; 11 12 // if we partition at a given position, we are looking for: 13 // sum of positives on left + sum of negatives on right 14 // no taken negative is to the left of a taken positive 15 // no taken positive is to the right of a taken negative 16 // given this, we have a hard constraint that we may only take negatives on the right and positives on the left if we want the current 17 // we can compute the prefix positive sum and suffix negative sum and add these, finding the max selection as we go 18 19 ll solve(vector<ll>& ls) { 20 21 vector<ll> prefixPositive {}; 22 vector<ll> suffixNegative (ls.size(), 0); 23 24 ll running = 0; 25 26 for(int i = 0; i < ls.size(); ++i) { 27 if(ls[i] > 0) { 28 running += ls[i]; 29 } 30 prefixPositive.push_back(running); 31 } 32 33 running = 0; 34 for(int i = ls.size()-1; i >= 0; --i) { 35 if(ls[i] < 0) { 36 running += ls[i] * -1; 37 } 38 suffixNegative[i] = running; 39 } 40 41 ll best = 0; 42 for(int i = 0; i < ls.size(); ++i) { 43 ll score = prefixPositive[i] + suffixNegative[i]; 44 best = max(score, best); 45 } 46 47 return best; 48 } 49 50 int main() { 51 52 ll testCases, n, current; 53 cin >> testCases; 54 55 for(int z = 0; z < testCases; ++z) { 56 cin >> n; 57 vector<ll> ls {}; 58 for(int i = 0; i < n; ++i) { 59 cin >> current; 60 ls.push_back(current); 61 } 62 cout << solve(ls) << endl; 63 } 64 }