Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

Maximum Points You Can Obtain from Cards

MEDIUMProblemSolveExternal Links

Description

There are several cards arranged in a row, and each card has an associated number of points. The points are given in the integer array cardPoints.

In one step, you can take one card from either the beginning (leftmost) or the end (rightmost) of the row. You must take exactly k cards in total.

Your score is the sum of the points of the cards you have taken. Given the integer array cardPoints and the integer k, return the maximum score you can obtain.

Examples

Example 1

Input: cardPoints = [1, 2, 3, 4, 5, 6, 1], k = 3

Output: 12

Explanation: You need to pick exactly 3 cards. The possible ways to pick from both ends and their scores are:

  • Take 0 from left, 3 from right: [5, 6, 1] → score = 12
  • Take 1 from left, 2 from right: [1] + [6, 1] → score = 8
  • Take 2 from left, 1 from right: [1, 2] + [1] → score = 4
  • Take 3 from left, 0 from right: [1, 2, 3] → score = 6

The maximum score is 12, achieved by taking all 3 cards from the right end.

Example 2

Input: cardPoints = [2, 2, 2], k = 2

Output: 4

Explanation: No matter which 2 cards you pick from the ends, each card is worth 2 points, so the score is always 2 + 2 = 4.

Example 3

Input: cardPoints = [9, 7, 7, 9, 7, 7, 9], k = 7

Output: 55

Explanation: Since k equals the total number of cards, you must take all 7 cards. The sum is 9 + 7 + 7 + 9 + 7 + 7 + 9 = 55.

Constraints

  • 1 ≤ cardPoints.length ≤ 10^5
  • 1 ≤ cardPoints[i] ≤ 10^4
  • 1 ≤ k ≤ cardPoints.length

Editorial

Brute Force

Intuition

Since we must pick exactly k cards and each card must come from either the left end or the right end of the row, there is a limited structure to the choices we can make. If we take i cards from the left side, we must take the remaining k - i cards from the right side. The value of i ranges from 0 (take nothing from the left) to k (take everything from the left).

This gives us exactly k + 1 possible splits to consider. Think of it like cutting a pie: you decide how large a slice to take from each end, and together the two slices must contain exactly k pieces.

The most direct approach is to try every split and compute the total score for each one. For a split where we take i cards from the left, we sum up cardPoints[0] through cardPoints[i-1], and for the k - i cards from the right, we sum up the last k - i elements. We keep track of the maximum score seen across all splits.

Step-by-Step Explanation

Let's trace through with cardPoints = [1, 2, 3, 4, 5, 6, 1], k = 3, n = 7:

Step 1: Initialize max_score = 0. We will try all splits from left = 0 to left = 3.

Step 2: Split (left = 0, right = 3). Take 0 from left, 3 from right.

  • Right cards: cardPoints[4..6] = [5, 6, 1]
  • Score = 5 + 6 + 1 = 12
  • 12 > 0, so update max_score = 12.

Step 3: Split (left = 1, right = 2). Take 1 from left, 2 from right.

  • Left cards: cardPoints[0] = [1]
  • Right cards: cardPoints[5..6] = [6, 1]
  • Score = 1 + 6 + 1 = 8
  • 8 < 12, max_score stays 12.

Step 4: Split (left = 2, right = 1). Take 2 from left, 1 from right.

  • Left cards: cardPoints[0..1] = [1, 2]
  • Right cards: cardPoints[6] = [1]
  • Score = 1 + 2 + 1 = 4
  • 4 < 12, max_score stays 12.

Step 5: Split (left = 3, right = 0). Take 3 from left, 0 from right.

  • Left cards: cardPoints[0..2] = [1, 2, 3]
  • Score = 1 + 2 + 3 = 6
  • 6 < 12, max_score stays 12.

Step 6: All k + 1 = 4 splits evaluated.

Result: max_score = 12, achieved by taking all 3 cards from the right end.

Brute Force — Trying All Left-Right Splits — Watch as we evaluate all k+1 possible ways to split the k cards between left and right ends, computing the total score for each split from scratch.

Algorithm

  1. Initialize max_score = 0.
  2. For each value of left from 0 to k:
    • Set right = k - left.
    • Compute left_sum = sum of the first left elements.
    • Compute right_sum = sum of the last right elements.
    • Set score = left_sum + right_sum.
    • Update max_score = max(max_score, score).
  3. Return max_score.

Code

class Solution {
public:
    int maxScore(vector<int>& cardPoints, int k) {
        int n = cardPoints.size();
        int maxScore = 0;
        
        for (int left = 0; left <= k; left++) {
            int right = k - left;
            int score = 0;
            
            // Sum the first 'left' cards
            for (int i = 0; i < left; i++) {
                score += cardPoints[i];
            }
            
            // Sum the last 'right' cards
            for (int i = n - right; i < n; i++) {
                score += cardPoints[i];
            }
            
            maxScore = max(maxScore, score);
        }
        
        return maxScore;
    }
};
class Solution:
    def maxScore(self, cardPoints: list[int], k: int) -> int:
        n = len(cardPoints)
        max_score = 0
        
        for left in range(k + 1):
            right = k - left
            
            # Sum the first 'left' cards and last 'right' cards
            score = sum(cardPoints[:left]) + sum(cardPoints[n - right:] if right > 0 else [])
            max_score = max(max_score, score)
        
        return max_score
class Solution {
    public int maxScore(int[] cardPoints, int k) {
        int n = cardPoints.length;
        int maxScore = 0;
        
        for (int left = 0; left <= k; left++) {
            int right = k - left;
            int score = 0;
            
            // Sum the first 'left' cards
            for (int i = 0; i < left; i++) {
                score += cardPoints[i];
            }
            
            // Sum the last 'right' cards
            for (int i = n - right; i < n; i++) {
                score += cardPoints[i];
            }
            
            maxScore = Math.max(maxScore, score);
        }
        
        return maxScore;
    }
}

Complexity Analysis

Time Complexity: O(k²)

We evaluate k + 1 splits. For each split, we compute the sum of up to k elements (some from the left, some from the right). In the worst case, each sum computation takes O(k) time. Therefore: (k + 1) splits × O(k) per split = O(k²).

For example, if k = 50,000, we would perform roughly 2.5 × 10^9 operations — far too slow.

Space Complexity: O(1)

We use only a few integer variables (loop counters, running score, max score). No additional data structures are needed.

Why This Approach Is Not Efficient

The brute force recomputes each split's sum entirely from scratch. With k up to 10^5, the O(k²) time complexity means up to 10^10 operations — orders of magnitude beyond acceptable limits.

The core waste: when we move from split (left = i, right = k - i) to split (left = i + 1, right = k - i - 1), the two sums differ by exactly one card on each side. We add cardPoints[i] to the left selection and remove one card from the right selection. Recomputing the entire sum throws away this incremental relationship.

The key insight: if we start with one extreme split (all k from the right) and then slide one card at a time — adding from the left while removing from the right — each transition costs only O(1). This transforms k + 1 sum computations of O(k) each into k + 1 transitions of O(1) each, giving us O(k) total time.

Optimal Approach - Sliding Window

Intuition

Rather than computing every split from scratch, we exploit the fact that consecutive splits differ by exactly one card on each side.

Picture a deck of cards spread out in a line. You start by grabbing the last k cards from the right end. Now, one by one, you "trade": you put back the leftmost card of your right selection and pick up the next available card from the left end. Each trade changes your total score by a small, easily calculated amount — you just add the new card's value and subtract the old card's value.

By tracking your running sum through all k trades, you explore every possible split in O(k) time without ever recomputing a full sum.

Concretely:

  • Start with the sum of the last k elements.
  • At each step i (for i = 0, 1, ..., k - 1), add cardPoints[i] (a new card from the left) and subtract cardPoints[n - k + i] (a card being returned to the right). Update the maximum if this new sum is better.

Step-by-Step Explanation

Let's trace through with cardPoints = [1, 2, 3, 4, 5, 6, 1], k = 3, n = 7:

Step 1: Start by taking all k = 3 cards from the right end.

  • Cards selected: [5, 6, 1] (indices 4, 5, 6)
  • current_sum = 5 + 6 + 1 = 12
  • max_score = 12

Step 2: Slide step i = 0. Add cardPoints[0] = 1 from the left. Remove cardPoints[n - k + 0] = cardPoints[4] = 5 from the right.

  • current_sum = 12 + 1 - 5 = 8
  • Cards now selected: [1] from left + [6, 1] from right
  • 8 < 12, max_score stays 12.

Step 3: Slide step i = 1. Add cardPoints[1] = 2 from the left. Remove cardPoints[n - k + 1] = cardPoints[5] = 6 from the right.

  • current_sum = 8 + 2 - 6 = 4
  • Cards now selected: [1, 2] from left + [1] from right
  • 4 < 12, max_score stays 12.

Step 4: Slide step i = 2. Add cardPoints[2] = 3 from the left. Remove cardPoints[n - k + 2] = cardPoints[6] = 1 from the right.

  • current_sum = 4 + 3 - 1 = 6
  • Cards now selected: [1, 2, 3] from left
  • 6 < 12, max_score stays 12.

Step 5: All k + 1 = 4 configurations explored.

Result: max_score = 12. The best strategy is to take all 3 cards from the right end.

Sliding Window — Incrementally Trading Right Cards for Left Cards — Watch how we start with all k cards from the right, then slide one card at a time from right to left. Each slide is an O(1) update to the running sum.

Algorithm

  1. Compute the initial sum of the last k elements: current_sum = sum(cardPoints[n-k .. n-1]).
  2. Set max_score = current_sum.
  3. For each i from 0 to k - 1:
    • Add cardPoints[i] to current_sum (take one more card from the left).
    • Subtract cardPoints[n - k + i] from current_sum (return one card to the right).
    • Update max_score = max(max_score, current_sum).
  4. Return max_score.

Code

class Solution {
public:
    int maxScore(vector<int>& cardPoints, int k) {
        int n = cardPoints.size();
        
        // Start with all k cards from the right
        int currentSum = 0;
        for (int i = n - k; i < n; i++) {
            currentSum += cardPoints[i];
        }
        int maxScore = currentSum;
        
        // Slide: replace right cards with left cards one at a time
        for (int i = 0; i < k; i++) {
            currentSum += cardPoints[i] - cardPoints[n - k + i];
            maxScore = max(maxScore, currentSum);
        }
        
        return maxScore;
    }
};
class Solution:
    def maxScore(self, cardPoints: list[int], k: int) -> int:
        n = len(cardPoints)
        
        # Start with all k cards from the right
        current_sum = sum(cardPoints[n - k:])
        max_score = current_sum
        
        # Slide: replace right cards with left cards one at a time
        for i in range(k):
            current_sum += cardPoints[i] - cardPoints[n - k + i]
            max_score = max(max_score, current_sum)
        
        return max_score
class Solution {
    public int maxScore(int[] cardPoints, int k) {
        int n = cardPoints.length;
        
        // Start with all k cards from the right
        int currentSum = 0;
        for (int i = n - k; i < n; i++) {
            currentSum += cardPoints[i];
        }
        int maxScore = currentSum;
        
        // Slide: replace right cards with left cards one at a time
        for (int i = 0; i < k; i++) {
            currentSum += cardPoints[i] - cardPoints[n - k + i];
            maxScore = Math.max(maxScore, currentSum);
        }
        
        return maxScore;
    }
}

Complexity Analysis

Time Complexity: O(k)

The initial sum of the last k elements takes O(k) time. The sliding loop runs exactly k iterations, each performing O(1) work (one addition, one subtraction, one max comparison). Total: O(k) + O(k) = O(k).

With k up to 10^5, this means at most ~10^5 operations — well within time limits.

Space Complexity: O(1)

We use only a constant number of variables: currentSum, maxScore, and the loop counter i. No arrays, hash maps, or other data structures that grow with the input are needed.