dp.cpp (2645B)
1 #include <iostream> 2 #include <deque> 3 #include <vector> 4 #include <unordered_set> 5 #include <unordered_map> 6 #include <algorithm> 7 #include <queue> 8 9 #define ll long long 10 11 using namespace std; 12 13 // array a of length n 14 // all are non-zero 15 // I have zero coins, will do the following until a is empty 16 // m := |a| (right now) 17 // select i such that 1 <= i <= m, gain abs(a_i) coins and then: 18 // if a_i < 0 then replace a with [a_1,a_2,...,a_{i-1}] (delete the suffix a_i) 19 // if a_i >= 0 then replace a with [a_{i+1}, a_{i+2}, ... , a_m] (delete the prefix of a_i inc) 20 // find max number of coins possible 21 22 // has to run in ~O(n) 23 24 // if selection < 0 then remove after inclusive 25 // if selection >= 0 then remove before inclusive 26 27 // 3 1 4 -1 -5 -9 28 29 // we can yank out 3,1,4 for "free" 30 // 3+1+4 = 8 31 // -1 -5 -9 32 // these are also free from the outside in. 33 // thus we have 9 + 8 + 5 + 1 = 23 34 35 36 // -10 -3 -17 1 19 20 37 // there are no free options. 38 // in this case we have to decide. 39 // do we want to take -17 or 1 40 // the left sums to 30, the right 40, so that one. 41 42 // at each step we either want to take the rightmost negative or leftmost positive 43 // well, which one? 44 45 // the dp approach would just be to try both, but that seems maybe too slow? 46 // maybe not actually, yeah, there don't seem to be any really bad cases for this. 47 48 // concretely: 49 // take the free ones 50 // check the two best options 51 52 ll prune(deque<int>& ls) { 53 ll res = 0; 54 while(ls.size() > 0 && (ls[0] > 0 || ls[ls.size()-1] < 0)) { 55 if(ls[0] > 0) { 56 res += ls[0]; 57 ls.pop_front(); 58 continue; 59 } 60 else { 61 res += ls[ls.size()-1] * -1; 62 ls.pop_back(); 63 } 64 } 65 return res; 66 } 67 68 ll solve(deque<int>& ls) { 69 70 ll res = 0; 71 res += prune(ls); 72 73 if(ls.size() == 0) { 74 return res; 75 } 76 77 78 deque<int> left = ls; 79 80 for(int i = ls.size()-1; i >= 0; --i) { 81 if(ls[i] < 0) { 82 break; 83 } 84 left.pop_back(); 85 } 86 87 ll bestLeft = solve(left); 88 89 deque<int> right = ls; 90 91 for(int i = 0; i < ls.size(); ++i) { 92 if(ls[i] > 0) { 93 break; 94 } 95 right.pop_front(); 96 } 97 98 ll bestRight = solve(right); 99 100 101 return res + max(bestLeft, bestRight); 102 } 103 104 int main() { 105 106 int testCases, n, current; 107 cin >> testCases; 108 109 for(int z = 0; z < testCases; ++z) { 110 cin >> n; 111 deque<int> ls {}; 112 for(int i = 0; i < n; ++i) { 113 cin >> current; 114 ls.push_back(current); 115 } 116 cout << solve(ls) << endl; 117 } 118 }