Maximum Points You Can Obtain from Cards
Maximum Points You Can Obtain from Cards: take exactly k cards, one at a time, from either end of the row. Return the maximum score obtainable.
- 1 <= cardPoints.length <= 10⁵
- 1 <= cardPoints[i] <= 10⁴
- 1 <= k <= cardPoints.length
Intuition
Maximum points you can obtain from cards takes exactly k cards, each from either end of the row, maximising the total. The ends-only rule makes this look like a two-pointer search, but the number of end-combinations is 2^k.
The reframing that collapses it is to think about what stays behind:
- Taking k cards from the two ends is the same as leaving a contiguous window of n − k cards in the middle, so maximising what is taken means minimising that window's sum.
That converts a choice problem into a fixed-size sliding window, which is linear.
So compute the total of all cards, then find the minimum sum of any contiguous subarray of length n − k. The answer is total − minWindowSum.
The window is fixed length, so the standard update applies — add the entering element, subtract the leaving one.
The edge case is k == n, where every card is taken and the leftover window has length 0. Its sum is 0 and the answer is the total. Some implementations mishandle a zero-length window, so it is worth checking explicitly or ensuring the loop degenerates safely.
The alternative keeps the ends explicit: take the first k cards, then swap them one at a time for cards from the right end, tracking the best total across all k + 1 splits. That is also O(k) and equally valid — some find it more intuitive since it mirrors the problem's wording.
Both are O(n) time and O(1) space; neither needs a prefix-sum array.
Taking from both ends is awkward; taking a contiguous block is easy. Since you always take exactly k cards, the ones left behind form a contiguous window of size n - k. Equivalently, start with the first k and slide cards from the front out and from the back in. Reframing an ends-problem as a window problem is the move.
Approach
Before reading on: price up what the direct approach costs here, then ask what running total makes each query a single subtraction. Aim for O(k) time and O(1) space.
Reframe as what remains
Taking k cards from the ends leaves a contiguous window of n - k in the middle. Maximising what is taken is minimising that window's sum — a fixed-size window problem.
Compute the total
Sum every card once. The answer will be this total minus the smallest leftover window.
Slide a fixed window
Find the minimum sum over all windows of length n - k, updating by adding the entering element and subtracting the leaving one.
Subtract for the answer
The result is total - minWindowSum. Every valid selection of end cards corresponds to exactly one such window, so nothing is missed.
Handle taking every card
When k == n the leftover window has length 0 and the answer is the total. Check this explicitly, since a zero-length window trips some implementations.
Know the explicit alternative
Take the first k cards, then swap them one at a time for cards from the right, tracking the best across all k + 1 splits. Equally O(k) and closer to the problem's wording.
Cost of the approach
One pass for the total and one for the window give O(n) time and O(1) space, with no prefix-sum array required.
Solution & live demo
Common pitfalls
Greedily taking the larger end each time
for _ in range(k):
if cardPoints[l] > cardPoints[r]: take l
else: take rfor i in range(1, k + 1):
total += cardPoints[n - i] - cardPoints[k - i]Greedy fails when a small card guards a large one — on [1, 100, 1] with k = 2 it takes the two 1s and misses the 100. Only considering all k + 1 split points finds the true optimum.
Getting the slide indices backwards
total += cardPoints[k - i] - cardPoints[n - i]
total += cardPoints[n - i] - cardPoints[k - i]
Each step gives back one card from the front of the prefix and takes one from the back of the array. Swapping the terms inverts the transaction and produces a monotonically shrinking, meaningless total.
Starting best at zero when values could be small
best = 0 total = sum(cardPoints[:k])
total = sum(cardPoints[:k]) best = total
The all-from-the-front split is itself a candidate and must be seeded as the initial best. Starting at 0 happens to be safe only because points are non-negative — seeding from the actual first window is correct regardless.
Edge cases
All cards are taken, so the answer is the total. The loop still runs and every split gives the same sum.
Only two splits exist — the first card or the last — and the maximum of the two is returned.
LeetCode constrains points to be positive, but the algorithm needs no change if they were not: it compares totals, never assuming any card is worth taking.
Every split gives the same total, which is returned.