algorithms

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

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 }