Maximum Points You Can Obtain from Cards — Medium Problem & Solution

Cards are laid out in a row. In one step you take a card from the beginning or the end of the row. You take exactly k cards.

Difficulty: Medium
Topics: Arrays, Sliding Window, Prefix Sum
Asked at: Amazon, Google, Razorpay
Time limit: 2 s
Memory limit: 256 MB
Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

Cards are laid out in a row. In one step you take a card from the beginning or the end of the row. You take exactly k cards.

Return the maximum total points you can collect.

Example 1

Input: cardPoints = [1,2,3,4,5,6,1], k = 3
Output: 12
Explanation: Take from the right: 1, 6, 5.

Example 2

Input: cardPoints = [2,2,2], k = 2
Output: 4

Example 3

Input: cardPoints = [9,7,7,9,7,7,9], k = 7
Output: 55
Explanation: Taking every card.

Constraints

1 <= cardPoints.length <= 100000
1 <= cardPoints[i] <= 10000
1 <= k <= cardPoints.length

How to solve Maximum Points You Can Obtain from Cards

Every valid choice takes i cards from the front and k - i from the back. Start from the all-front case and move one card at a time from the front group to the back group, which is a constant-time update.

Approach

Sum the first k cards — the all-prefix choice.
For i from 1 to k, swap one card: add cardPoints[n - i] and subtract cardPoints[k - i].
Track the maximum.

Why it works

Taking from either end means the taken cards always form a prefix and a suffix, so the k + 1 splits enumerate every possibility. The roll keeps each step constant time, and the equivalent 'minimise the untouched middle window' view is the same computation read the other way round.

Complexity

Time — O(k)
Space — O(1)

Pitfalls

k can equal n, where the middle window is empty and the answer is the whole sum.
Enumerating all 2^k sequences of moves is exponential and unnecessary — only the split matters.
The total reaches 10^9, at the edge of int.

Reference solution

Python

from typing import List

def maxScore(cardPoints: List[int], k: int) -> int:
    n = len(cardPoints)
    total = sum(cardPoints[:k])
    best = total
    for i in range(1, k + 1):
        total += cardPoints[n - i] - cardPoints[k - i]
        best = max(best, total)
    return best

JavaScript

var maxScore = function(cardPoints, k) {
    var n = cardPoints.length, sum = 0, i;
    for (i = 0; i < k; i++) sum += cardPoints[i];
    var best = sum;
    for (i = 1; i <= k; i++) {
        sum += cardPoints[n - i] - cardPoints[k - i];
        if (sum > best) best = sum;
    }
    return best;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 667 arrays problems · the whole catalogue