#1423
Maximum Points You Can Obtain from Cards
Medium Window on the complement
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Cards are in a row. Take exactly k cards, each from either the left or right end. Maximise the sum of taken cards.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: take k cards from the two ends to maximise points.
Why this works: whatever you take, the cards left form one block of n - k in the middle. Minimise that block's sum.
Example: [1, 2, 3, 4, 5, 6, 1], k = 3, total 22
windows of length 4: 10, 14, 18, 16smallest 10 → 22 - 10 = 12
✦Hints open one at a time
Whatever you take, the cards left behind form a contiguous block of length n − k.
Maximising what you take = minimising the sum of that middle block.
↗Approach
Find the minimum-sum window of size n - k with a fixed sliding window, and subtract it from the total.
</>Solution (Java)
class Solution {
public int maxScore(int[] cardPoints, int k) {
int n = cardPoints.length, w = n - k, total = 0;
for (int x : cardPoints) total += x;
int sum = 0;
for (int i = 0; i < w; i++) sum += cardPoints[i];
int minWindow = sum;
for (int i = w; i < n; i++) {
sum += cardPoints[i] - cardPoints[i - w];
minWindow = Math.min(minWindow, sum);
}
return total - minWindow; // cards taken = everything except the middle block
}
}!Common mistake
Trying greedy "take the bigger end each time" — it fails when a big card hides behind a small one.
Complexity
- Time: O(n).
- Space: O(1).
Topic: Sliding Window
🎬 Episode 10: video coming soon