Maximum Points You Can Obtain from Cards

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 the beginning or from the end of the row. You have to take exactly k cards.

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.

Example 1:

Input: cardPoints = [1,2,3,4,5,6,1], k = 3 Output: 12 Explanation: After the first step, your score will always be 1. However, choosing the rightmost card first will maximize your total score. The optimal strategy is to take the three cards on the right, giving a final score of 1 + 6 + 5 = 12.

Example 2:

Input: cardPoints = [2,2,2], k = 2 Output: 4 Explanation: Regardless of which two cards you take, your score will always be 4.

Example 3:

Input: cardPoints = [9,7,7,9,7,7,9], k = 7 Output: 55 Explanation: You have to take all the cards. Your score is the sum of points of all cards.

Constraints:

• 1 <= cardPoints.length <= 105
• 1 <= cardPoints[i] <= 104
• 1 <= k <= cardPoints.length

Approach: Sliding Window on the Remaining Cards (Complement Window)

Algorithm

1. The total number of points minus the maximum score of the n - k middle cards equals the answer
2. Compute the total sum of all cards
3. Use a sliding window of size n - k and find its minimum sum
4. Return totalSum - minWindowSum

Time & Space Complexity

• Time Complexity: O(n) - single pass over the array
• Space Complexity: O(1) - constant extra space

Java Implementation

public class MaximumPointsYouCanObtainFromCards {

    /**
     * Return the maximum score by taking exactly k cards from the ends.
     * @param cardPoints Points of each card
     * @param k Number of cards to take
     * @return Maximum possible score
     */
    public static int maxScore(int[] cardPoints, int k) {
        int n = cardPoints.length;
        int total = 0;
        for (int p : cardPoints) {
            total += p;
        }

        int windowSize = n - k;
        if (windowSize == 0) {
            return total;
        }

        int windowSum = 0;
        for (int i = 0; i < windowSize; i++) {
            windowSum += cardPoints[i];
        }

        int minWindow = windowSum;
        for (int i = windowSize; i < n; i++) {
            windowSum += cardPoints[i] - cardPoints[i - windowSize];
            minWindow = Math.min(minWindow, windowSum);
        }

        return total - minWindow;
    }

    // Test method
    public static void main(String[] args) {
        int[] cards1 = {1, 2, 3, 4, 5, 6, 1};
        int k1 = 3;
        System.out.println("Input: cardPoints = [1,2,3,4,5,6,1], k = 3");
        System.out.println("Output: " + maxScore(cards1, k1)); // Expected: 12

        int[] cards2 = {2, 2, 2};
        int k2 = 2;
        System.out.println("Input: cardPoints = [2,2,2], k = 2");
        System.out.println("Output: " + maxScore(cards2, k2)); // Expected: 4

        int[] cards3 = {9, 7, 7, 9, 7, 7, 9};
        int k3 = 7;
        System.out.println("Input: cardPoints = [9,7,7,9,7,7,9], k = 7");
        System.out.println("Output: " + maxScore(cards3, k3)); // Expected: 55
    }
}

Example Walkthrough

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

1. total = 22
2. windowSize = 7 - 3 = 4
3. Find the minimum sum of a 4-card contiguous window: [1,2,3,4]=10, [2,3,4,5]=14, [3,4,5,6]=18, [4,5,6,1]=16. Minimum is 10
4. Answer = 22 - 10 = 12

Key Points

1. Complement Idea: Taking k cards from the ends leaves a contiguous block of n - k cards in the middle
2. Minimize the Middle: The middle block’s sum must be minimized to maximize the taken score
3. Sliding Window: Track the minimum of all fixed-size windows in O(n)
4. O(1) Space: Only a few variables are needed
5. Edge Case: When k == n, all cards are taken