☕ DSA Java Articles

Topics › Sliding Window and Two Pointers › Medium Problems

Maximum Points You Can Obtain from Cards

Medium TUF ID 922 A2Z

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

Cards are laid out in a row, and cardPoints[i] is the score of card i. In one move you take a card from either the left end or the right end of the row. You must make exactly k moves. Return the maximum total score you can collect.

The order of moves does not matter, only how many cards come from each end. Taking left cards from the front and k - left from the back always yields the first left cards plus the last k - left cards, whatever order you take them in. So there are just k + 1 possible outcomes, one per value of left from 0 to k.

Constraints: 1 ≤ n ≤ 10^5, 1 ≤ cardPoints[i] ≤ 10^4, 1 ≤ k ≤ n. The total of all cards is at most 10^9, which fits in an int.

Example 1

cardPoints = [1, 2, 3, 4, 5, 6, 1], k = 3
answer = 12         // take the three rightmost cards: 1 + 6 + 5

Example 2

cardPoints = [1, 79, 80, 1, 1, 1, 200, 1], k = 3
answer = 202        // one from the left (1) and two from the right (1 + 200)

A greedy rule such as “always take the larger end” does not work, because a large card can hide behind a small one. On [1, 100, 5, 2] with k = 2, greedy takes 2 and then 5 for a total of 7, while taking both left cards gives 101. You have to compare whole splits.

Approach 1: Brute force over the split

Intuition. Try every split directly. For each left from 0 to k, add up the first left cards and the last k - left cards, and keep the maximum. This is already far better than simulating every sequence of moves (2^k of them), but it recomputes each sum from scratch.

Algorithm.

  1. For left = 0 .. k:
    • sum = first left cards + last k - left cards.
    • Update best.
  2. Return best.
static int bruteForce(int[] cardPoints, int k) {
    int n = cardPoints.length, best = Integer.MIN_VALUE;
    for (int left = 0; left <= k; left++) {
        int sum = 0;
        for (int i = 0; i < left; i++) sum += cardPoints[i];
        for (int i = 0; i < k - left; i++) sum += cardPoints[n - 1 - i];
        best = Math.max(best, sum);
    }
    return best;
}

Complexity. Time O(k^2): k + 1 splits, each summing k cards. Space O(1). With k = 10^5 that is 10^10 additions, far too slow.

Approach 2: Optimal, slide the split point

Intuition. Neighbouring splits differ by a single card. Going from left cards on the left to left - 1, we give back card left - 1 (the innermost card taken from the left) and take one more card from the right end. So start with all k cards from the left, then perform k trades, updating two running sums in O(1) each time.

You can picture this as a window of k cards that “wraps around” the end of the array: it starts at [0 .. k-1] and rotates step by step until it is [n-k .. n-1].

Algorithm.

  1. leftSum = sum of the first k cards; rightSum = 0; best = leftSum.
  2. For i = k - 1 down to 0:
    • leftSum -= cardPoints[i].
    • rightSum += cardPoints[n - k + i] (when i = k - 1 this is the last card n - 1, then n - 2, and so on).
    • Update best with leftSum + rightSum.
  3. Return best.
static int optimal(int[] cardPoints, int k) {
    int n = cardPoints.length, leftSum = 0, rightSum = 0;
    for (int i = 0; i < k; i++) leftSum += cardPoints[i];
    int best = leftSum;
    for (int i = k - 1; i >= 0; i--) {
        leftSum -= cardPoints[i];                  // give back the innermost left card
        rightSum += cardPoints[n - k + i];         // take one more card from the right end
        best = Math.max(best, leftSum + rightSum);
    }
    return best;
}

Dry run on cardPoints = [1, 2, 3, 4, 5, 6, 1], k = 3, n = 7:

step removed from left added from right leftSum rightSum total best
start     1+2+3 = 6 0 6 6
i = 2 3 index 6: 1 3 1 4 6
i = 1 2 index 5: 6 1 7 8 8
i = 0 1 index 4: 5 0 12 12 12

Complexity. Time O(k): one pass to build the first sum and k constant-time trades. Space O(1).

Approach 3: Alternative optimal, minimise what you leave behind

Intuition. Whatever split you choose, the cards you do not take form one contiguous block of exactly n - k cards in the middle. Maximising the cards taken is the same as minimising the sum of that block, because the two add up to the fixed total. So the problem becomes the classic fixed-size sliding window: find the minimum sum over all windows of length w = n - k, and subtract it from the total.

This view is worth knowing because “choose from both ends” problems frequently turn into “choose one middle block” problems, which are often easier to reason about.

Algorithm.

  1. total = sum of all cards; w = n - k.
  2. windowSum = sum of the first w cards; minWindow = windowSum.
  3. For i = w .. n - 1: slide by adding cardPoints[i] and removing cardPoints[i - w]; update minWindow.
  4. Return total - minWindow.
static int minWindowComplement(int[] cardPoints, int k) {
    int n = cardPoints.length, w = n - k, total = 0;
    for (int x : cardPoints) total += x;
    int windowSum = 0;
    for (int i = 0; i < w; i++) windowSum += cardPoints[i];
    int minWindow = windowSum;
    for (int i = w; i < n; i++) {
        windowSum += cardPoints[i] - cardPoints[i - w];
        minWindow = Math.min(minWindow, windowSum);
    }
    return total - minWindow;
}

Complexity. Time O(n): one pass for the total and one sliding pass. Space O(1). This is slower than Approach 2 when k is much smaller than n, and equally fast when k is close to n.

When k = n, the window has length 0: every slide adds and removes the same card, minWindow stays 0, and the answer is the full total, as it should be.

Edge cases and pitfalls