Maximum Points You Can Obtain from Cards

Problem

Given a row of cards and an integer k, pick exactly k cards from either the beginning or the end of the row to maximize the total score.

Input:  cardPoints = [1,2,3,4,5,6,1], k = 3
Output: 12   (take last three: 6+1+... actually first one + last two: 1+6+... best is 4+5+... )

Python Solution

def max_score(card_points, k):
    n = len(card_points)
    window_size = n - k
    if window_size == 0:
        return sum(card_points)
    total = sum(card_points)
    window_sum = sum(card_points[:window_size])
    min_window = window_sum
    for i in range(window_size, n):
        window_sum += card_points[i] - card_points[i - window_size]
        min_window = min(min_window, window_sum)
    return total - min_window

C++ Solution

int maxScore(vector<int>& cardPoints, int k) {
    int n = cardPoints.size();
    int windowSize = n - k;
    int total = 0;
    for (int c : cardPoints) total += c;
    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 = min(minWindow, windowSum);
    }
    return total - minWindow;
}

Java Solution

class Solution {
    public int maxScore(int[] cardPoints, int k) {
        int n = cardPoints.length;
        int windowSize = n - k;
        int total = 0;
        for (int c : cardPoints) total += c;
        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;
    }
}

Complexity

Time: O(n) — one pass to total the array, one sliding pass to find the minimum middle window. Space: O(1) — only running sums are kept. The key trick: picking k cards from the ends is the same as leaving out the minimum-sum contiguous window of size n-k from the middle.