Maximum Points You Can Obtain from Cards
Maximum Points You Can Obtain from Cards is a medium arrays & hashing problem solved with the sliding window · fixed pattern.
The best approach, optimal (sliding window over the ends), runs in O(k) time and O(1) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (try every split, recompute sums) up.
Problem
A row of cards lies on the table, and cardPoints[i] is the score printed on card i. You make exactly k moves; in each move you pick up either the leftmost or the rightmost card that is still in the row, and its points are added to your score.
Return the highest total score you can reach after k moves.
Examples
Example 1
- Input
cardPoints = [6, 2, 1, 1, 9, 4], k = 3- Output
19- Why
- Take 6 from the left and 4, 9 from the right: 6 + 4 + 9 = 19.
Example 2
- Input
cardPoints = [4, 4, 4], k = 3- Output
12- Why
- k equals the number of cards, so every card is taken.
Example 3
- Input
cardPoints = [1, 50, 1, 1, 3], k = 1- Output
3- Why
- Only the two ends are reachable with one pick; the 50 in the middle is out of reach.
Constraints
1 <= cardPoints.length <= 10^51 <= cardPoints[i] <= 10^41 <= k <= cardPoints.length
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (3 examples, or your own). Submit also runs 12 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (try every split, recompute sums) | O(k²) | O(1) |
| Optimal (sliding window over the ends) | O(k) | O(1) |
1Brute force (try every split, recompute sums)
O(k²)k + 1 splits, each summed in O(k).O(1)Only running sums are stored.Every valid pick takes i cards from the front and k - i from the back, for some i between 0 and k. For each i, add up those cards from scratch and keep the best total.
- For i from 0 to k: sum the first i cards and the last k - i cards.
- Track the maximum of these sums.
- Return the maximum.
class Solution {
public int maxScore(int[] cardPoints, int k) {
int n = cardPoints.length;
int best = 0;
for (int i = 0; i <= k; i++) {
int sum = 0;
for (int a = 0; a < i; a++) {
sum += cardPoints[a];
}
for (int b = n - (k - i); b < n; b++) {
sum += cardPoints[b];
}
best = Math.max(best, sum);
}
return best;
}
}class Solution:
def maxScore(self, cardPoints: List[int], k: int) -> int:
n = len(cardPoints)
best = 0
for i in range(k + 1):
total = 0
for a in range(i):
total += cardPoints[a]
for b in range(n - (k - i), n):
total += cardPoints[b]
best = max(best, total)
return bestclass Solution {
public:
int maxScore(vector<int>& cardPoints, int k) {
int n = cardPoints.size();
int best = 0;
for (int i = 0; i <= k; i++) {
int sum = 0;
for (int a = 0; a < i; a++) {
sum += cardPoints[a];
}
for (int b = n - (k - i); b < n; b++) {
sum += cardPoints[b];
}
best = max(best, sum);
}
return best;
}
};function maxScore(cardPoints, k) {
const n = cardPoints.length;
let best = 0;
for (let i = 0; i <= k; i++) {
let sum = 0;
for (let a = 0; a < i; a++) {
sum += cardPoints[a];
}
for (let b = n - (k - i); b < n; b++) {
sum += cardPoints[b];
}
best = Math.max(best, sum);
}
return best;
}2Optimal (sliding window over the ends)
O(k)k cards to build the first sum, then k constant-time slides.O(1)Only the running sum and the best value.Start with all k cards taken from the front. Then, one step at a time, give back the innermost front card and take the next card from the back. Each step changes the total by one subtraction and one addition, so all k + 1 splits are scored in O(k).
- sum = cardPoints[0] + ... + cardPoints[k - 1]; best = sum.
- For j from 1 to k: sum -= cardPoints[k - j]; sum += cardPoints[n - j]; best = max(best, sum).
- Return best.
class Solution {
public int maxScore(int[] cardPoints, int k) {
int n = cardPoints.length;
int sum = 0;
for (int i = 0; i < k; i++) {
sum += cardPoints[i];
}
int best = sum;
for (int j = 1; j <= k; j++) {
sum -= cardPoints[k - j];
sum += cardPoints[n - j];
best = Math.max(best, sum);
}
return best;
}
}class Solution:
def maxScore(self, cardPoints: List[int], k: int) -> int:
n = len(cardPoints)
total = sum(cardPoints[:k])
best = total
for j in range(1, k + 1):
total -= cardPoints[k - j]
total += cardPoints[n - j]
best = max(best, total)
return bestclass Solution {
public:
int maxScore(vector<int>& cardPoints, int k) {
int n = cardPoints.size();
int sum = 0;
for (int i = 0; i < k; i++) {
sum += cardPoints[i];
}
int best = sum;
for (int j = 1; j <= k; j++) {
sum -= cardPoints[k - j];
sum += cardPoints[n - j];
best = max(best, sum);
}
return best;
}
};function maxScore(cardPoints, k) {
const n = cardPoints.length;
let sum = 0;
for (let i = 0; i < k; i++) {
sum += cardPoints[i];
}
let best = sum;
for (let j = 1; j <= k; j++) {
sum -= cardPoints[k - j];
sum += cardPoints[n - j];
best = Math.max(best, sum);
}
return best;
}Edge cases to test
- k equals the number of cards: the answer is the total sum
- k = 1: the larger of the two end cards
- The best choice takes every card from one side only
- A large value in the middle that greedy end-picking cannot reach
Hints
Hint 1
Picking greedily the larger end each time can fail. What do all valid selections have in common?
Hint 2
Any selection is some i cards from the left and k - i cards from the right. There are only k + 1 such splits.
Hint 3
Moving from split i to split i + 1 changes the sum by one card in and one card out: slide the window instead of recomputing.
FAQ
What is the best time complexity for Maximum Points You Can Obtain from Cards?
Optimal (sliding window over the ends) runs in O(k) time and O(1) extra space. k cards to build the first sum, then k constant-time slides.
Which pattern does Maximum Points You Can Obtain from Cards use?
It is a arrays & hashing problem that uses the sliding window · fixed pattern. Other problems with the same pattern: Maximum Average Subarray I, K Radius Subarray Averages, Maximum Number of Vowels in a Substring of Given Length.
Is there a brute force solution for Maximum Points You Can Obtain from Cards?
Yes. Brute force (try every split, recompute sums) takes O(k²) time and O(1) space. Every valid pick takes i cards from the front and k - i from the back, for some i between 0 and k.
Which edge cases should I test for Maximum Points You Can Obtain from Cards?
k equals the number of cards: the answer is the total sum; k = 1: the larger of the two end cards; The best choice takes every card from one side only; A large value in the middle that greedy end-picking cannot reach.