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.
Solution
Visualization
Python
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
Unlock Premium Coding Content
Reading Progress
On This Page
Your account is free and you can post anonymously if you choose.