Maximum Points You Can Obtain from Cards
WHAT IT SAYS
Given a row of cards and a number k, take exactly k cards — one at a time, from either end — to maximise the total you collect.
WHAT IT'S REALLY ASKING
"The problem is dressed up as a sequence of decisions, but you can't lose a card by taking it later: whatever order you pick in, you end up holding some cards off the front and some off the back. So you're not choosing k moves, you're choosing one number — how deep to bite from the left — and the rest is forced."
Recurse on the choice: front or back?
O(2^k) time, O(k) stackAt each of the k turns you can take the leftmost or the rightmost remaining card, so branch on both, recurse with k − 1 picks left, and return the better of the two. It explores every legal sequence of moves, so it's certainly correct.
WHERE THE WORK IS WASTED — The tree has 2^k leaves but only k + 1 distinct outcomes, and you can point at the collisions: 'take front, then back' and 'take back, then front' are two separate branches that end holding the identical two cards for the identical score. In general, all C(k, i) paths that take i cards from the front and k − i from the back land on the exact same hand — you re-derive one answer an exponential number of times, purely because you're tracking the order of the picks when the score doesn't depend on it.
The order is a decoy. Only the split survives.
Every pick removes a card from one end, so the cards you've removed always form a prefix and a suffix — never a hole in the middle, because a middle card can't be reached until everything outside it is gone. After k picks you are therefore holding the first i cards and the last k − i cards, for some i between 0 and k. That's true of every possible play sequence, no exceptions. And the score is a sum, which doesn't care what order you added things in. So two play sequences that end on the same i score identically — the order you chose them in is information the problem never reads. The 2^k decision tree collapses to k + 1 candidate hands, one per split, and the answer is simply the best of them. Once you see that, the second thing follows for free: if you take a prefix of i and a suffix of k − i, the cards you *leave behind* are one contiguous run of exactly n − k cards. Maximising what you take is the same as minimising what you abandon — and what you abandon is a fixed-size window.
Slide the split
O(k) time, O(1) spaceStart by taking the first k cards and remember the sum. Then, k times, hand the deepest front card back and take one more from the back instead — each swap is two additions, so you walk all k + 1 splits in O(k) total. The largest sum you see is the answer.
Or look at what's left over
O(n) time, O(1) spaceTotal up every card once. The leftovers are always a contiguous window of size n − k, so slide a fixed-size window of that width across the array, track the smallest sum it ever holds, and subtract it from the total. Same answer, and it's the version that generalises: the moment the problem says 'remove elements from the ends', the survivors are a window.
Order-Blind Split
YOU'LL SEE IT AGAIN WHEN
- You're asked for a sequence of moves, but each move only touches the ends of a structure — so the set of things removed is always a prefix plus a suffix, whatever order you chose.
- The objective is a sum, max, or count over the chosen items — something order-independent — so two different play orders reaching the same set are the same answer.
- The naive formulation branches exponentially while the number of genuinely distinct end states is linear in the input.
- The complement of your choice (what you didn't take) is contiguous and fixed in size, which turns 'maximise what I take' into 'minimise a window'.