algorithms

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

commit b63e5a3222ab104556e607146d9bd4c63bd2f2c9
parent 6b82bda0d15204fd7682cb63f8f238bd05b7e5e5
Author: Andrew Laack <andrew@laack.co>
Date:   Tue, 17 Nov 2026 09:10:34 -0600

Remove the ends, greedy 1300, div3 c

Diffstat:
Acomp/remove-the-ends/dp.cpp | 118+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Acomp/remove-the-ends/ex1.in | 7+++++++
Acomp/remove-the-ends/ex2.in | 0
Acomp/remove-the-ends/main.cpp | 64++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Acomp/remove-the-ends/thoughts.txt | 0
5 files changed, 189 insertions(+), 0 deletions(-)

diff --git a/comp/remove-the-ends/dp.cpp b/comp/remove-the-ends/dp.cpp @@ -0,0 +1,118 @@ +#include <iostream> +#include <deque> +#include <vector> +#include <unordered_set> +#include <unordered_map> +#include <algorithm> +#include <queue> + +#define ll long long + +using namespace std; + +// array a of length n + // all are non-zero +// I have zero coins, will do the following until a is empty + // m := |a| (right now) + // select i such that 1 <= i <= m, gain abs(a_i) coins and then: + // if a_i < 0 then replace a with [a_1,a_2,...,a_{i-1}] (delete the suffix a_i) + // if a_i >= 0 then replace a with [a_{i+1}, a_{i+2}, ... , a_m] (delete the prefix of a_i inc) +// find max number of coins possible + +// has to run in ~O(n) + +// if selection < 0 then remove after inclusive +// if selection >= 0 then remove before inclusive + +// 3 1 4 -1 -5 -9 + +// we can yank out 3,1,4 for "free" +// 3+1+4 = 8 +// -1 -5 -9 +// these are also free from the outside in. +// thus we have 9 + 8 + 5 + 1 = 23 + + +// -10 -3 -17 1 19 20 +// there are no free options. +// in this case we have to decide. +// do we want to take -17 or 1 +// the left sums to 30, the right 40, so that one. + +// at each step we either want to take the rightmost negative or leftmost positive +// well, which one? + +// the dp approach would just be to try both, but that seems maybe too slow? +// maybe not actually, yeah, there don't seem to be any really bad cases for this. + +// concretely: + // take the free ones + // check the two best options + +ll prune(deque<int>& ls) { + ll res = 0; + while(ls.size() > 0 && (ls[0] > 0 || ls[ls.size()-1] < 0)) { + if(ls[0] > 0) { + res += ls[0]; + ls.pop_front(); + continue; + } + else { + res += ls[ls.size()-1] * -1; + ls.pop_back(); + } + } + return res; +} + +ll solve(deque<int>& ls) { + + ll res = 0; + res += prune(ls); + + if(ls.size() == 0) { + return res; + } + + + deque<int> left = ls; + + for(int i = ls.size()-1; i >= 0; --i) { + if(ls[i] < 0) { + break; + } + left.pop_back(); + } + + ll bestLeft = solve(left); + + deque<int> right = ls; + + for(int i = 0; i < ls.size(); ++i) { + if(ls[i] > 0) { + break; + } + right.pop_front(); + } + + ll bestRight = solve(right); + + + return res + max(bestLeft, bestRight); +} + +int main() { + + int testCases, n, current; + cin >> testCases; + + for(int z = 0; z < testCases; ++z) { + cin >> n; + deque<int> ls {}; + for(int i = 0; i < n; ++i) { + cin >> current; + ls.push_back(current); + } + cout << solve(ls) << endl; + } +} diff --git a/comp/remove-the-ends/ex1.in b/comp/remove-the-ends/ex1.in @@ -0,0 +1,7 @@ +3 +6 +3 1 4 -1 -5 -9 +6 +-10 -3 -17 1 19 20 +1 +1 diff --git a/comp/remove-the-ends/ex2.in b/comp/remove-the-ends/ex2.in diff --git a/comp/remove-the-ends/main.cpp b/comp/remove-the-ends/main.cpp @@ -0,0 +1,64 @@ +#include <iostream> +#include <vector> +#include <unordered_set> +#include <unordered_map> +#include <algorithm> +#include <queue> + +#define ll long long + +using namespace std; + +// if we partition at a given position, we are looking for: + // sum of positives on left + sum of negatives on right + // no taken negative is to the left of a taken positive + // no taken positive is to the right of a taken negative + // 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 + // we can compute the prefix positive sum and suffix negative sum and add these, finding the max selection as we go + +ll solve(vector<ll>& ls) { + + vector<ll> prefixPositive {}; + vector<ll> suffixNegative (ls.size(), 0); + + ll running = 0; + + for(int i = 0; i < ls.size(); ++i) { + if(ls[i] > 0) { + running += ls[i]; + } + prefixPositive.push_back(running); + } + + running = 0; + for(int i = ls.size()-1; i >= 0; --i) { + if(ls[i] < 0) { + running += ls[i] * -1; + } + suffixNegative[i] = running; + } + + ll best = 0; + for(int i = 0; i < ls.size(); ++i) { + ll score = prefixPositive[i] + suffixNegative[i]; + best = max(score, best); + } + + return best; +} + +int main() { + + ll testCases, n, current; + cin >> testCases; + + for(int z = 0; z < testCases; ++z) { + cin >> n; + vector<ll> ls {}; + for(int i = 0; i < n; ++i) { + cin >> current; + ls.push_back(current); + } + cout << solve(ls) << endl; + } +} diff --git a/comp/remove-the-ends/thoughts.txt b/comp/remove-the-ends/thoughts.txt