Sliding Window
Max Points You Can Obtain From Cards
medium
Count: 10
DESCRIPTION (inspired by Leetcode.com)
Given an array of integers representing card values, write a function to calculate the maximum score you can achieve by picking exactly k cards.
You must pick cards in order from either end. You can take some cards from the beginning, then switch to taking cards from the end, but you cannot skip cards or pick from the middle.
For example, with k = 3:
- Take the first 3 cards: valid
- Take the last 3 cards: valid
- Take the first card, then the last 2 cards: valid
- Take the first 2 cards, then the last card: valid
- Take card at index 0, skip some, then take card at index 5: not valid (skipping cards)
Constraints: 1 <= k <= cards.length
Example 1: Input:
cards = [2,11,4,5,3,9,2] k = 3
Output:
17
Explanation:
- First 3 cards: 2 + 11 + 4 = 17
- Last 3 cards: 3 + 9 + 2 = 14
- First 1 + last 2: 2 + 9 + 2 = 13
- First 2 + last 1: 2 + 11 + 2 = 15
Maximum score is 17.
Example 2: Input:
cards = [1, 100, 10, 0, 4, 5, 6] k = 3
Output:
111
Explanation: Take the first three cards: 1 + 100 + 10 = 111. This is better than taking the last 3 cards (4 + 5 + 6 = 15) or any other combination.
Explanation
When you pick k cards from either end of the array, you're actually leaving behind n - k consecutive cards in the middle that you didn't pick.
For example, with cards = [2,11,4,5,3,9,2] and k = 3:
Every possible way to pick 3 cards from the ends corresponds to a different window of 4 cards (n - k = 7 - 3 = 4) in the middle that we're NOT picking.
Why This Matters
Since we know the total sum of all cards, we can calculate:
Sum of picked cards = Total sum - Sum of unpicked cards
So to maximize the sum of picked cards, we need to minimize the sum of unpicked cards.
This transforms the problem: instead of trying all combinations of picking from ends, we find the minimum sum of any window of size n - k.
Sum of picked cards (highlighted) = 36 - 23 = 13
The Algorithm
Use a fixed-length sliding window of size n - k to find the minimum sum of any consecutive n - k cards. For each window position, calculate total - window_sum to get the corresponding score, and track the maximum.
This runs in O(n) time and O(1) space. When k is much smaller than n, you can skip the middle of the array entirely. Start with the first k cards as your pick. Then, one step at a time, give back the innermost card from the front and take the next card from the back. After k steps you've tried all k + 1 splits, so the work is O(k):
def maxScore(cards, k):
n = len(cards)
state = sum(cards[:k])
max_points = state
for i in range(1, k + 1):
state += cards[n - i] - cards[k - i]
max_points = max(max_points, state)
return max_pointsIt's still a fixed-length sliding window. The window has size k and wraps around the end of the array, instead of being the n - k cards you leave behind.
Solution
Visualization
Try these examples:
def maxScore(cards, k):total = sum(cards)if k == len(cards):return totalstate = 0max_points = 0start = 0for end in range(len(cards)):state += cards[end]if end - start + 1 == len(cards) - k:max_points = max(total - state, max_points)state -= cards[start]start += 1return max_points
start
max points from cards
0 / 18
Mark as read
Your account is free and you can post anonymously if you choose.