Maximum Points You Can Obtain from Cards

You are given an integer array cardPoints and an integer k. In one move, you can take one card from the beginning or the end of the array. Your task is to return the maximum score you can obtain by choosing exactly k cards.

Input: cardPoints = [1,2,3,4,5,6,1], k = 3
Output: 12
Explanation: Pick the cards [1, 6, 5] or [6, 5, 1], total = 12.

Understanding the Problem

We are given an array called cardPoints, and an integer k. Imagine you are playing a game where you can pick exactly k cards, but only from the start or end of the array—never from the middle.

Your goal is to get the maximum possible score by picking k cards in total, from either end. The score is simply the sum of the selected cards.

For example, given:

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

You can choose the cards [1, 6, 5] (from end and start), and their sum is 12. This is the highest possible score with 3 cards.

Step-by-Step Solution with Example

Step 1: Understand the Brute Force Approach

If we try every combination of k cards from the front and back, the number of possibilities is large. For example:

• Take all 3 cards from the front: [1, 2, 3]
• Take 2 from front and 1 from back: [1, 2, 1]
• Take 1 from front and 2 from back: [1, 6, 1]
• Take all 3 from the back: [6, 1, 5]

We can’t afford to try all combinations for large arrays. So we need an efficient method.

Step 2: Use Sliding Window Intuition

Here’s the key trick: instead of choosing which k cards to take, we can think of which n-k cards to leave out in the middle. Why?

Because you’re only allowed to pick cards from the two ends. So the cards you don’t pick are a continuous segment in the middle of the array.

Step 3: Calculate Total Sum and Find Minimum Middle Window

We first calculate the total sum of all the cards — this is the score if we could pick all cards.

Then, we find the minimum sum of any subarray of length n - k (i.e., the unpicked cards). We subtract this from the total to get the maximum score.

cardPoints = [1, 2, 3, 4, 5, 6, 1], k = 3
Total cards = 7
We need to skip a window of 7 - 3 = 4 cards.

Try all subarrays of length 4:
[1, 2, 3, 4] → sum = 10  
[2, 3, 4, 5] → sum = 14  
[3, 4, 5, 6] → sum = 18  
[4, 5, 6, 1] → sum = 16  

Minimum sum = 10 (skip these 4 cards)
Total sum = 1+2+3+4+5+6+1 = 22  
Max score = 22 - 10 = 12

Step 4: Code It with Sliding Window

We can use a sliding window of size n - k to compute this efficiently without checking all subarrays manually.

Edge Cases

• k = cardPoints.length: You take all the cards, return the total sum.
• k = 0: You take no cards, score is 0.
• All elements are equal: Any selection of k cards will result in the same total score.
• Large values at both ends: Choosing from both ends should be considered (e.g., [1000, 1, 1, 1, 1000]).

Final Thoughts

This is a classic example of converting a selection problem into a window-based optimization. Instead of brute-force checking all combinations of taking cards from both ends, we slide a window over the part we skip and subtract it from the total. This makes the solution efficient and elegant.

Sliding window techniques are powerful when the problem involves contiguous subarrays or a fixed number of operations across a range. Always look for ways to turn the problem "inside out" like we did here.

1. Calculate the total sum of the last k cards and store it as the initial maxScore.
2. Use a sliding window of size k, where you move the window from the end of the array towards the start.
3. In each step, remove one card from the end of the current window and add one card from the front of the array.
4. Track the updated sum after each step and update maxScore accordingly.
5. Repeat this process k times to check all combinations of cards taken from front and back.
6. Return maxScore as the result.

from typing import List

def max_points_from_cards(cardPoints: List[int], k: int) -> int:
    n = len(cardPoints)
    current_sum = sum(cardPoints[n - k:])
    max_score = current_sum
    for i in range(k):
        current_sum += cardPoints[i] - cardPoints[n - k + i]
        if current_sum > max_score:
            max_score = current_sum
    return max_score

# Example usage
card_points = [1, 2, 3, 4, 5, 6, 1]
k = 3
print(max_points_from_cards(card_points, k))  # Output: 12

public class MaxPointsFromCards {
    public static int maxPoints(int[] cardPoints, int k) {
        int n = cardPoints.length;
        int currentSum = 0;
        for (int i = n - k; i < n; i++) {
            currentSum += cardPoints[i];
        }
        int maxScore = currentSum;
        for (int i = 0; i < k; i++) {
            currentSum += cardPoints[i] - cardPoints[n - k + i];
            if (currentSum > maxScore) {
                maxScore = currentSum;
            }
        }
        return maxScore;
    }

    public static void main(String[] args) {
        int[] cardPoints = {1, 2, 3, 4, 5, 6, 1};
        int k = 3;
        System.out.println(maxPoints(cardPoints, k));  // Output: 12
    }
}

function maxPoints(cardPoints, k) {
  const n = cardPoints.length;
  let currentSum = 0;
  for (let i = n - k; i < n; i++) {
    currentSum += cardPoints[i];
  }
  let maxScore = currentSum;
  for (let i = 0; i < k; i++) {
    currentSum += cardPoints[i] - cardPoints[n - k + i];
    if (currentSum > maxScore) maxScore = currentSum;
  }
  return maxScore;
}

// Example usage
const cardPoints = [1, 2, 3, 4, 5, 6, 1];
const k = 3;
console.log(maxPoints(cardPoints, k));  // Output: 12

#include <stdio.h>

int maxPoints(int* cardPoints, int n, int k) {
    int currentSum = 0;
    for (int i = n - k; i < n; i++) {
        currentSum += cardPoints[i];
    }
    int maxScore = currentSum;
    for (int i = 0; i < k; i++) {
        currentSum += cardPoints[i] - cardPoints[n - k + i];
        if (currentSum > maxScore) {
            maxScore = currentSum;
        }
    }
    return maxScore;
}

int main() {
    int cardPoints[] = {1, 2, 3, 4, 5, 6, 1};
    int k = 3;
    int n = sizeof(cardPoints) / sizeof(cardPoints[0]);
    printf("%d\n", maxPoints(cardPoints, n, k));  // Output: 12
    return 0;
}

#include <iostream>
#include <vector>
using namespace std;

int maxPoints(vector<int>& cardPoints, int k) {
    int n = cardPoints.size();
    int currentSum = 0;
    for (int i = n - k; i < n; i++) {
        currentSum += cardPoints[i];
    }
    int maxScore = currentSum;
    for (int i = 0; i < k; i++) {
        currentSum += cardPoints[i] - cardPoints[n - k + i];
        if (currentSum > maxScore) {
            maxScore = currentSum;
        }
    }
    return maxScore;
}

int main() {
    vector<int> cardPoints = {1, 2, 3, 4, 5, 6, 1};
    int k = 3;
    cout << maxPoints(cardPoints, k) << endl;  // Output: 12
    return 0;
}

package main

import "fmt"

func maxPoints(cardPoints []int, k int) int {
    n := len(cardPoints)
    currentSum := 0
    for i := n - k; i < n; i++ {
        currentSum += cardPoints[i]
    }
    maxScore := currentSum
    for i := 0; i < k; i++ {
        currentSum += cardPoints[i] - cardPoints[n-k+i]
        if currentSum > maxScore {
            maxScore = currentSum
        }
    }
    return maxScore
}

func main() {
    cardPoints := []int{1, 2, 3, 4, 5, 6, 1}
    k := 3
    fmt.Println(maxPoints(cardPoints, k)) // Output: 12
}

fn max_points(card_points: &[i32], k: usize) -> i32 {
    let n = card_points.len();
    let mut current_sum: i32 = card_points[n - k..].iter().sum();
    let mut max_score = current_sum;
    for i in 0..k {
        current_sum += card_points[i] - card_points[n - k + i];
        if current_sum > max_score {
            max_score = current_sum;
        }
    }
    max_score
}

fn main() {
    let card_points = vec![1, 2, 3, 4, 5, 6, 1];
    let k = 3;
    println!("{}", max_points(&card_points, k)); // Output: 12
}

fun maxPoints(cardPoints: IntArray, k: Int): Int {
    val n = cardPoints.size
    var currentSum = cardPoints.sliceArray(n - k until n).sum()
    var maxScore = currentSum
    for (i in 0 until k) {
        currentSum += cardPoints[i] - cardPoints[n - k + i]
        if (currentSum > maxScore) {
            maxScore = currentSum
        }
    }
    return maxScore
}

fun main() {
    val cardPoints = intArrayOf(1, 2, 3, 4, 5, 6, 1)
    val k = 3
    println(maxPoints(cardPoints, k)) // Output: 12
}

func maxPoints(_ cardPoints: [Int], _ k: Int) -> Int {
    let n = cardPoints.count
    var currentSum = cardPoints[(n - k)...].reduce(0, +)
    var maxScore = currentSum
    for i in 0 ..< k {
        currentSum += cardPoints[i] - cardPoints[n - k + i]
        if currentSum > maxScore {
            maxScore = currentSum
        }
    }
    return maxScore
}

let cardPoints = [1, 2, 3, 4, 5, 6, 1]
let k = 3
print(maxPoints(cardPoints, k)) // Output: 12

function maxPoints(cardPoints: number[], k: number): number {
  const n = cardPoints.length;
  let currentSum = 0;
  for (let i = n - k; i < n; i++) {
    currentSum += cardPoints[i];
  }
  let maxScore = currentSum;
  for (let i = 0; i < k; i++) {
    currentSum += cardPoints[i] - cardPoints[n - k + i];
    if (currentSum > maxScore) maxScore = currentSum;
  }
  return maxScore;
}

// Example usage
const cardPoints = [1, 2, 3, 4, 5, 6, 1];
const k = 3;
console.log(maxPoints(cardPoints, k)); // Output: 12

Time complexity

Space complexity

O(1)

Only a fixed number of variables are used to maintain the current score, max score, and intermediate sums. No additional data structures are used regardless of the input size.