Course4all
Join us on telegram
Home/dsa/Sliding Window/Maximum Points You Can Obtain from Cards

Maximum Points You Can Obtain from Cards

Master this topic with zero to advance depth.

Maximum Points You Can Obtain from Cards

You can take exactly k cards from either the beginning or the end of the row to maximize your point total.

Visual Representation

cardPoints = [1, 2, 3, 4, 5, 6, 1], k = 3 Take cards from ends (Total: 7, k: 3): (1, 2) ... (1) Total: 4 (1) ... (6, 1) Total: 8 ... ... (5, 6, 1) Total: 12 (MAX) Trick: Minimize the sum of the remaining (n-k) cards! Remaining window size = 7 - 3 = 4
Medium

Examples

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

Level I: Brute Force

Intuition

Try all possible combinations of taking i cards from the left and k - i cards from the right (where 0 <= i <= k). For each combination, calculate the sum and track the maximum.

Thought Process

  1. Let i be the number of cards from the left end.
  2. Then k - i cards must be taken from the right end.
  3. Iterate i from 0 to k.
  4. Calculate Sum = (Sum of first i) + (Sum of last k - i).
  5. Tracking the maximum sum.
⏱ O(K^2) or O(K) with prefix sums💾 O(1)

Detailed Dry Run

Cards from LeftCards from RightTotal Sum
03 (5, 6, 1)12
1 (1)2 (6, 1)8
2 (1, 2)1 (1)4
3 (1, 2, 3)06
java
public class Main {
    public static int maxScore(int[] cardPoints, int k) {
        int maxScore = 0;
        int n = cardPoints.length;
        for (int i = 0; i <= k; i++) {
            int currentScore = 0;
            // Left i cards
            for (int j = 0; j < i; j++) currentScore += cardPoints[j];
            // Right k-i cards
            for (int j = 0; j < k - i; j++) currentScore += cardPoints[n - 1 - j];
            maxScore = Math.max(maxScore, currentScore);
        }
        return maxScore;
    }

    public static void main(String[] args) {
        System.out.println(maxScore(new int[]{1, 2, 3, 4, 5, 6, 1}, 3)); // 12
    }
}
Approach 2

Level III: Optimal (Sliding Window)

Intuition

Thought Process

Selecting k cards from the ends is equivalent to leaving n - k contiguous cards in the middle. To maximize the end cards, we must minimize the sum of the middle cards. This turns it into a fixed-size sliding window problem on the inner subarray.

Patterns

  1. Inverse Goal: Instead of picking ends, find the minimum middle.
  2. Fixed Window: The middle part always has size n - k.
⏱ O(N)💾 O(1)

Detailed Dry Run

WindowSumMin SumAction
[1, 2, 3, 4]1010Initial
[2, 3, 4, 5]1410Slide
[3, 4, 5, 6]1810Slide
[4, 5, 6, 1]1610Slide
java
public class Main {
    public static int maxScore(int[] cardPoints, int k) {
        int n = cardPoints.length, total = 0, windowSum = 0;
        for (int p : cardPoints) total += p;
        if (k == n) return total;
        int windowSize = n - k;
        for (int i = 0; i < windowSize; i++) windowSum += cardPoints[i];
        int minWindowSum = windowSum;
        for (int i = windowSize; i < n; i++) {
            windowSum += cardPoints[i] - cardPoints[i - windowSize];
            minWindowSum = Math.min(minWindowSum, windowSum);
        }
        return total - minWindowSum;
    }

    public static void main(String[] args) {
        System.out.println(maxScore(new int[]{1, 2, 3, 4, 5, 6, 1}, 3));
    }
}

⚠️ Common Pitfalls & Tips

While you can use recursion with memoization, the sliding window approach is much faster and uses O(1) extra space. The 'inverse' trick is the most important leap.

← Previous QuestionMinimum Window Subsequence
Next Question →Longest Subarray of 1's After Deleting One Element