main.cpp (2396B)
1 #include <vector> 2 #include <unordered_map> 3 #include <iostream> 4 5 // issues: 6 // this is too slow for inputs of n up to 200_000 7 // this implementation will not be able to store large enough values given the array size and numeric distribution 8 9 // - compute best from given state where: 10 // - state := (left,right) 11 12 // ex: 13 // 3 14 // 6 15 // 3 1 4 -1 -5 -9 16 // 6 17 // -10 -3 -17 1 19 20 18 // 1 19 // 1 20 21 using namespace std; 22 23 // memo: 24 // (left,right) 25 // left << 32, right 26 // tighter: 27 // we can stop if any left value < current or any right value > right has a higher value than current because it's 'inclusive' 28 // is there some sort of prefix sum list thing we want then? 29 // this would be a combined prefix / suffix sum, but I'd think this'd be too large? 30 // perhaps not, inputs only up to size of 200_000, actually likely so 31 // hmm, actually maybe not 32 // we'd've likely already been in this current state by that point 33 34 // alt framing: 35 // left, size 36 // do comparison for sizes and see if better approach exists for a larger size? 37 // this comparison array would be one per left value and have a size of n 38 // 200_000 * 200_000 = 40_000_000_000 39 // that's too big. 40 41 long long solve(vector<int>& ls, int left, int right, unordered_map<long long, long long>& memo) { 42 43 long long current = (((long long)left) << 32) | right; 44 45 if(memo.contains(current)) { 46 return memo[current]; 47 } 48 49 if(left > right) { 50 memo[current] = 0; 51 return 0; 52 } 53 54 long long best = 0; 55 56 57 for(int i = left; i <= right; ++i) { 58 int removedScore = abs(ls[i]); 59 if(ls[i] < 0){ 60 long long current = solve(ls, left, i-1, memo); 61 best = max(removedScore+current,best); 62 } else { 63 long long current = solve(ls, i+1, right, memo); 64 best = max(removedScore+current,best); 65 } 66 } 67 68 memo[current] = best; 69 return best; 70 71 } 72 73 int main() { 74 int testCases, len, current = 0; 75 cin >> testCases; 76 for(int z = 0; z < testCases; ++z) { 77 78 cin >> len; 79 vector<int> ls {}; 80 81 for(int i = 0; i < len; ++i) { 82 cin >> current; 83 ls.push_back(current); 84 } 85 86 unordered_map<long long, long long> memo {}; 87 cout << solve(ls,0,ls.size()-1,memo) << endl; 88 } 89 }