Pattern visualizer
Maximum Points You Can Obtain from Cards
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. 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..
Fixed-size window over the cards you DON'T take
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