Maximum Points You Can Obtain from Cards
Find the maximum score you can get by taking k cards from either end of the row.
Problem Understanding
A row of cards each carries a point value, and you must take exactly k of them.
Constraint: In each step, you can take one card from either the beginning or the end of the row.
Goal: maximize the total points of the cards you have taken.
Example:
nums = [1, 2, 3, 4, 5, 6, 1],k = 3- Output:
12 - Explanation: Take
[1, 2]from left and[1]from right? Sum = 4.
Or take[1]from left and[6, 1]from right? Sum = 8.
Or take[5, 6, 1]from right? Sum = 12. (Max)
Algorithm Strategy
Instead of simulating every decision (Recursion/DP), which is slow, realize that we always select k cards total. If we take i cards from the left, we must take k - i cards from the right.
The Sliding Window Approach:
- Start: Assume we take all
kcards from the beginning (left side). Calculate thiscurrent_sum. - Slide: In each step, we give up one card from the left and take one card from the right.
- Subtract
card[k - 1 - i](the rightmost card of our left selection). - Add
card[n - 1 - i](the corresponding card from the end of the array).
- Subtract
- Track: Keep track of the maximum sum found during this sliding process.
Visual Walkthrough
Watch how we start with the first k cards, then progressively swap a left card for a right card to find the optimal combination.
Dry Run: [1, 2, 3, 4, 5, 6, 1], k=3
| Step | Left Pick (Indices) | Right Pick (Indices) | Removed | Added | Sum | Max |
|---|---|---|---|---|---|---|
| Init | [0, 1, 2] (Val: 1, 2, 3) |
[] |
- | - | 6 | 6 |
| 1 | [0, 1] (Val: 1, 2) |
[6] (Val: 1) |
Index 2 (3) | Index 6 (1) | 6-3+1 = 4 |
6 |
| 2 | [0] (Val: 1) |
[6, 5] (Val: 1, 6) |
Index 1 (2) | Index 5 (6) | 4-2+6 = 8 |
8 |
| 3 | [] |
[6, 5, 4] (Val: 1, 6, 5) |
Index 0 (1) | Index 4 (5) | 8-1+5 = 12 |
12 |
| End | Result: 12 |
Edge Cases & Tips
Edge Cases:
- k = n: We must take all cards. Return the total sum of the array.
- k = 0: No cards taken, sum is 0 (though usually
k >= 1).
Common Mistake:
- Thinking this is a standard DP problem. Since we only take from ends, the remaining cards always form a contiguous subarray in the middle. Minimizing the middle subarray sum is equivalent to maximizing the ends.
Code Solution
Implementation using the sliding window strategy:
Maximum Points You Can Obtain from Cards Code
1var maxScore = function(cardPoints, k) {2 let leftSum = 0;3 for (let i = 0; i < k; i++) leftSum += cardPoints[i];45 let maxScore = leftSum;6 let rightSum = 0;7 const n = cardPoints.length;89 for (let i = 0; i < k; i++) {10 leftSum -= cardPoints[k - 1 - i];11 rightSum += cardPoints[n - 1 - i];12 maxScore = Math.max(maxScore, leftSum + rightSum);13 }14 return maxScore;15};