algorithms

Algorithm implementations
git clone git://git.laack.co/algorithms.git
Log | Files | Refs | README

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 }