algorithms

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

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 }