Maximum Points You Can Obtain from Cards
Fixed-size window over the cards you DON'T take
Picking from two ends looks like a decision tree with 2^k branches, but the cards left behind give it away: whatever order the ends are picked in, the untouched cards are always one contiguous block of n - k in the middle. Every possible set of k taken cards corresponds to exactly one such block, and vice versa. So maximising what is taken is the same as minimising what is left, and that is a plain fixed-width window: price the leftmost block once, then slide it right one card at a time, adding the card that enters and subtracting the card that leaves. The answer is the total of all cards minus the cheapest block found.
Details
Animated on: cardPoints = [5,2,8,1,1,9,3,6,4], k = 6 — take exactly k cards, one at a time, from either end, and maximise their total.
Problem:Maximum Points You Can Obtain from CardsMedium
Fixed-size window over the cards you DON'T take
step 1 / 9
Taking 6 of these 9 cards from the two ends always leaves the SAME shape behind: one unbroken block of 3 cards in the middle. So instead of choosing which 6 to take, choose which 3 to leave — and since the whole row is worth 39, leaving the cheapest block keeps the most points.
1FUNCTION maxScore(cards, k):2 n <- LENGTH(cards)3 w <- n - k4 total <- SUM(cards, 0, n - 1)5 curr <- SUM(cards, 0, w - 1)6 minSum <- curr7 FOR r <- w TO n - 1:8 curr <- curr + cards[r] - cards[r - w]9 minSum <- MIN(minSum, curr)10 RETURN total - minSum
← / → step · space play · Home restart
Every step in words
Show all 9 steps
- Taking 6 of these 9 cards from the two ends always leaves the SAME shape behind: one unbroken block of 3 cards in the middle. So instead of choosing which 6 to take, choose which 3 to leave — and since the whole row is worth 39, leaving the cheapest block keeps the most points.
- Start with the leftmost block of 3: 5 + 2 + 8 = 15. That is the case where all 6 cards come off the right end, and it is the cheapest block seen so far simply because it is the only one seen so far.
- Slide one card right: index 0 (worth 5) drops out and index 3 (worth 1) comes in, so the block sum goes 15 - 5 + 1 = 11 without re-adding the 3 cards from scratch. 11 undercuts the previous cheapest block of 15, so indices 1..3 become the block to leave behind.
- Slide one card right: index 1 (worth 2) drops out and index 4 (worth 1) comes in, so the block sum goes 11 - 2 + 1 = 10 without re-adding the 3 cards from scratch. 10 undercuts the previous cheapest block of 11, so indices 2..4 become the block to leave behind.
- Slide one card right: index 2 (worth 8) drops out and index 5 (worth 9) comes in, so the block sum goes 10 - 8 + 9 = 11 without re-adding the 3 cards from scratch. 11 is not cheaper than the best of 10, so the block at indices 2..4 still wins.
- Slide one card right: index 3 (worth 1) drops out and index 6 (worth 3) comes in, so the block sum goes 11 - 1 + 3 = 13 without re-adding the 3 cards from scratch. 13 is not cheaper than the best of 10, so the block at indices 2..4 still wins.
- Slide one card right: index 4 (worth 1) drops out and index 7 (worth 6) comes in, so the block sum goes 13 - 1 + 6 = 18 without re-adding the 3 cards from scratch. 18 is not cheaper than the best of 10, so the block at indices 2..4 still wins.
- Slide one card right: index 5 (worth 9) drops out and index 8 (worth 4) comes in, so the block sum goes 18 - 9 + 4 = 13 without re-adding the 3 cards from scratch. 13 is not cheaper than the best of 10, so the block at indices 2..4 still wins.
- Every block of 3 has been priced and the cheapest is indices 2..4, worth only 10. Leaving it means taking 2 cards off the left and 4 off the right — 5 + 2 + 9 + 3 + 6 + 4 — so the score is the whole row minus that block: 39 - 10 = 29.
Now solve it yourself
Watching is the first half. The second is writing it without the animation.