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.
- 1 <= k <= cardPoints.length <= 10⁵
- 1 <= cardPoints[i] <= 10^4
- Must take exactly k cards
cardPoints = [1,2,3,4,5,6,1], k = 312cardPoints = [2,2,2], k = 24cardPoints = [9,7,7,9,7,7,9], k = 755You 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.
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.
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.
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.
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.
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_windowm == 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.m = 7 − 3 = 4 cards, so slide a width-4 window and find its minimum sum.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.
Points from Cards
Inversion Insight
Picking k cards from the ends is the exact same as leaving n-k cards in the middle. To maximize the ends, we simply minimize the middle!
Step-by-Step Logic
Step 1: Problem: Take 3 cards from ends. Total sum 22. Strategy: Minimize middle 4 cards.