MediumArraysSliding WindowPrefix Sum

Maximum Points You Can Obtain from Cards

1 approach, code in every language

A row of cards each carries a point value, and you must take exactly k of them. On every pick you may only remove a card from the very front or the very back of the row. Choose your picks so the total of the chosen cards is as large as possible.

Instead of deciding which ends to draw from, flip the problem around: the cards you leave behind always form one contiguous block of size length minus k in the middle. Maximising what you take is the same as leaving behind the cheapest possible middle block.

Example 1

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

Output: 12

Taking 1 from the front and 6 then 5 from the back collects 12 points, which is the best any three end-picks can do.

Example 2

Input: cardPoints = [9,7,7,9,7,7,9], k = 7

Output: 55

With k equal to the whole row, every card must be taken, so the answer is the total of all values.

Constraints

1 ≤ cardPoints.length ≤ 10^5
1 ≤ cardPoints[i] ≤ 10^4
1 ≤ k ≤ cardPoints.length

Minimize the untaken middle window

The untaken cards form a fixed-size contiguous window of length n minus k; slide it to find the smallest interior sum and subtract that from the grand total.

Loading animation…

Intuition

Whatever combination of front and back picks you make, the leftover cards are always a single contiguous run in the middle whose length is exactly n minus k. The score you keep equals the total of all cards minus that leftover run. So rather than juggling two ends, slide a fixed-width window across the array to find the run with the smallest sum, and the maximum score is simply the total minus that minimum.

Algorithm walkthrough

1Compute the sum of every card, and let the leftover window width be n minus k.
2If that width is zero you must take every card, so return the total directly.
3Sum the first window of that width to seed the current and minimum leftover sums.
4Slide the window one step at a time, adding the entering card and removing the leaving card, tracking the smallest leftover sum.
5Return the total minus the smallest leftover sum found.

Implementation

class Solution:
    def maxScore(self, cardPoints: List[int], k: int) -> int:
        n = len(cardPoints)
        window = n - k
        total = sum(cardPoints)
        if window == 0:
            return total
        current = sum(cardPoints[:window])
        min_window = current
        for i in range(window, n):
            current += cardPoints[i] - cardPoints[i - window]
            min_window = min(min_window, current)
        return total - min_window

Time

O(n)

Space

O(1)

One pass totals the cards and a second pass slides the fixed window, both linear.

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Arrays

After the pattern

Now solve one you haven't seen.

Forklift Picks from the Crate Row is our own problem on the technique behind Maximum Points You Can Obtain from Cards: a new statement, so there's no answer to remember. Write it in your browser and run it against graded tests.

Practise it with tests All practice problems

1,194 problems · 15,062 graded tests · free