Algorithm

Max Points from Cards

Sliding Window Pattern

Maximum Points from Cards

There are several cards arranged in a row, and each card has an associated number of points. The points are given in the integer array cardPoints. In one step, you can take one card from the beginning or from the end of the row. You have to take exactly k cards. Your score is the sum of the points of the cards you have taken. Given the integer array cardPoints and the integer k, return the maximum score you can obtain.

CONSTRAINTS
  • 1 <= k <= cardPoints.length <= 10⁵
  • 1 <= cardPoints[i] <= 10^4
  • Must take exactly k cards
EXAMPLE 1
Input: cardPoints = [1,2,3,4,5,6,1], k = 3
Output: 12
Total sum = 22. Minimum middle window of size 4: [1,2,3,4]=10, [2,3,4,5]=14, [3,4,5,6]=18, [4,5,6,1]=16. Min is 10. Answer = 22 - 10 = 12.
EXAMPLE 2
Input: cardPoints = [2,2,2], k = 2
Output: 4
Take 2 cards from either end. The middle window of size 1 always has value 2. Answer = total(6) - min_middle(2) = 4.
EXAMPLE 3
Input: cardPoints = [9,7,7,9,7,7,9], k = 7
Output: 55
k equals n, so take all 7 cards. The middle window has size 0. Answer is the total sum = 55.
Can I take cards from the middle?
No. You can only take cards from the left end or the right end. The remaining cards form a contiguous block in the middle.
Must I take exactly k cards?
Yes. Exactly k cards — no more, no fewer.
Can I mix cards from both ends?
Yes. You can take i cards from the left and k-i from the right, for any i from 0 to k.
What if k equals n?
Taking all cards means the middle window has size 0 and sum 0. The answer is simply the total sum of all cards.

You take exactly k cards, but only ever from the two ends of the row — some number from the left, the rest from the right. You want the biggest possible total. At first this looks nothing like a sliding window: your picks are split across two far-apart ends, not one contiguous block. The trick is to stop looking at what you take and look at what you leave.

Trying every split is too slow

The direct idea is to try every way to divide the k picks between the two ends: take 0 from the left and k from the right, then 1 and k-1, and so on — or, as a recursion, at each step choose the left card or the right card.

python
def max_points_recursive(cards, k, left, right):
    if k == 0:
        return 0
    take_left  = cards[left]  + max_points_recursive(cards, k-1, left+1, right)
    take_right = cards[right] + max_points_recursive(cards, k-1, left, right-1)
    return max(take_left, take_right)

The recursion branches two ways at every one of the k steps, so it explores on the order of 2^k paths. With k up to 10⁵ that is hopeless. Even the tidier "try each left-count from 0 to k and sum both ends" is O(k) sums each costing O(k) — quadratic. We need a single pass.

Look at what you leave, not what you take

Here is the turn. Whatever k cards you take from the two ends, the cards you don't take are always the same shape: one solid contiguous block sitting in the middle, exactly n - k cards wide. Take 2 from the left and 1 from the right, and the leftover is the middle chunk between them. There is no way to take from the ends and leave a gap in the middle — the leftover is always one unbroken run.

The total of all cards is fixed. So your score = total − (the middle block you leave behind). To make your score as large as possible, make the block you leave behind as small as possible. The problem just flipped from "pick k scattered cards to maximize" into "find the contiguous block of size n - k with the minimum sum" — and that is a plain fixed-size window.

The Insighttaking from both ends leaves one fixed-width block in the middle; maximizing what you take equals minimizing that block, which is exactly Maximum Sum Subarray in reverse.
Fixed window on the leftover

Set m = n - k, the width of the block we leave. Slide a window of width m across the row with the same rolling-sum trick from Maximum Sum Subarray — add the incoming card, subtract the outgoing one — and keep the smallest window sum. The answer is the grand total minus that minimum.

python
def max_score(cardPoints, k):
    n = len(cardPoints)
    m = n - k                       # width of the block we leave behind
    total = sum(cardPoints)
    if m == 0:                      # k == n: we take everything
        return total
    window = sum(cardPoints[:m])    # first middle block, built once
    min_window = window
    for i in range(m, n):
        window += cardPoints[i] - cardPoints[i - m]   # +incoming, -outgoing
        min_window = min(min_window, window)
    return total - min_window
Crucial Notewatch the m == 0 case. When k == n you take every card, the leftover block has width 0, and there is no window to slide — the loop would never run and the answer is simply the total. Handle it before building the window.
Worked Example:cardPoints = [1,2,3,4,5,6,1], k = 3
Total = 22. We leave behind m = 7 − 3 = 4 cards, so slide a width-4 window and find its minimum sum.
- First block [1,2,3,4] = 10. min = 10.
- add 5, drop 1 → [2,3,4,5] = 14.
- add 6, drop 2 → [3,4,5,6] = 18.
- add 1, drop 3 → [4,5,6,1] = 16.
- Smallest middle block is [1,2,3,4] = 10, so the best score is 22 − 10 = 12. Leaving that block means taking everything to its right — cards 5, 6, 1 — which is exactly 3 cards from the right end, summing to 12.
The pattern hiding in disguise

The window here is the same fixed-size machine from Maximum Sum Subarray — same width, same running sum, same one-in/one-out fold. The only new idea is the reframe before the window: the thing the question asks you to optimize (edge picks) is not directly a window, but its complement is. Whenever a total is fixed and you must maximize one part, you can instead minimize the rest — and if that "rest" is forced to be one contiguous fixed-size block, a sliding window drops out.

Recognition signal for this disguised version: you can only act on the ends of a sequence, or the "chosen" part is scattered but the leftover is provably contiguous and of fixed size. When you feel a window is right but the target isn't contiguous, ask whether its complement is. If it is, run the window on the complement and subtract.

Interactive Strategy Visualization

Points from Cards

k=3 Cards
Inversion Trick
1
0
2
1
3
2
4
3
5
4
6
5
1
6
Middle Window Sum
--
O(2ᵏ) Try Every Pick
O(K²) Enumerate Splits
O(N) Fixed Window on the Complement