Maximum Points You Can Obtain from Cards
Medium · Sliding Window · Array · Sliding Window · Prefix Sum
Problem
Cards lie in a row, and cardPoints[i] is the score of card i. You must take exactly k cards, one at a time, and each card you take must come from either the left end or the right end of the remaining row.
Your score is the total of the cards you take. Return the maximum possible score.
Examples
Input: cardPoints = [2,9,1,1,8,3], k = 3 Output: 14
Taking 2 and 9 from the left and 3 from the right scores 14.
Input: cardPoints = [5,5,5], k = 3 Output: 15
k equals the number of cards, so you take all of them.
Input: cardPoints = [1,79,80,1,1,1,200,1], k = 3 Output: 202
Taking 1 from the right exposes 200: 1 + 200 + 1 = 202 beats any hand from the left.
Constraints
- 1 <= len(cardPoints) <= 10^5
- 1 <= cardPoints[i] <= 10^4
- 1 <= k <= len(cardPoints)
Approaches
- Baseline: sum every split from scratch — time O(k²), space O(1)
Follow-up
Equivalently, the cards you leave behind form a contiguous block of n - k cards, so the best score is the total minus the smallest sum of any window of length n - k. Both views are O(n); the one used here touches only 2k cards.
Related problems
Start free on Cariara · Coding problems · System design studio
