Maximum Points You Can Obtain from Cards

medium array sliding window prefix sum

Problem

Given an array cardPoints and integer k, take exactly k cards from either end. Return the maximum total score. Equivalent to: minimize the sum of an (n − k)-length contiguous subarray in the middle, then subtract from the total.

InputcardPoints = [1,2,3,4,5,6,1], k = 3

Output12

Take 1, 6, 5 from the right side: 1+6+5 = 12.

cardPoints (comma-separated)

def max_score(card_points, k):
    n = len(card_points)
    total = sum(card_points)
    win = n - k
    if win == 0: return total
    cur = sum(card_points[:win])
    mn = cur
    for i in range(win, n):
        cur += card_points[i] - card_points[i - win]
        if cur < mn: mn = cur
    return total - mn

function maxScore(cardPoints, k) {
  const n = cardPoints.length;
  let total = 0;
  for (const x of cardPoints) total += x;
  const win = n - k;
  if (win === 0) return total;
  let cur = 0;
  for (let i = 0; i < win; i++) cur += cardPoints[i];
  let mn = cur;
  for (let i = win; i < n; i++) {
    cur += cardPoints[i] - cardPoints[i - win];
    if (cur < mn) mn = cur;
  }
  return total - mn;
}

class Solution {
    public int maxScore(int[] cardPoints, int k) {
        int n = cardPoints.length, total = 0;
        for (int x : cardPoints) total += x;
        int win = n - k;
        if (win == 0) return total;
        int cur = 0;
        for (int i = 0; i < win; i++) cur += cardPoints[i];
        int mn = cur;
        for (int i = win; i < n; i++) {
            cur += cardPoints[i] - cardPoints[i - win];
            if (cur < mn) mn = cur;
        }
        return total - mn;
    }
}

int maxScore(vector<int>& cardPoints, int k) {
    int n = cardPoints.size(), total = 0;
    for (int x : cardPoints) total += x;
    int win = n - k;
    if (win == 0) return total;
    int cur = 0;
    for (int i = 0; i < win; i++) cur += cardPoints[i];
    int mn = cur;
    for (int i = win; i < n; i++) {
        cur += cardPoints[i] - cardPoints[i - win];
        if (cur < mn) mn = cur;
    }
    return total - mn;
}

Explanation

We take exactly k cards from the two ends, so the cards we leave behind always form one contiguous block of n - k cards in the middle. Picking the best ends is the same as leaving the worst middle.

So instead of trying all end combinations, we minimize the sum of a fixed-size window of width win = n - k as it slides across the array. The answer is the total of all cards minus that minimum middle sum.

We seed the window on the first win cards, then slide it: add the entering card cardPoints[i] and drop the leaving card cardPoints[i - win], tracking the smallest sum mn. (If win == 0 we simply take everything.)

Example: cardPoints = [1,2,3,4,5,6,1], k = 3, so win = 4. Total is 22. The lightest 4-card middle window is [2,3,4,1] summing to 10, so the score is 22 - 10 = 12.

Turning a "take from both ends" puzzle into one sliding window makes it a clean linear-time scan with constant space.

Time: O(n) Space: O(1)