⚡Flashcard Drill➔
NeetCode #792LC-1423MediumGreedy
← Back to All Problems

#792 · #1423 · Maximum Points You Can Obtain from Cards(可获得的最大点数)

📌 Problem Statement & Constraints

There are several cards in a row with cardPoints[i] points. In each step you take one card from either the beginning or the end. You must take exactly k cards. Return the maximum score. Constraints: 1 <= k <= cardPoints.length <= 10^5, 1 <= cardPoints[i] <= 10^4.

💡 Core Algorithmic Approaches

  1. Taking k cards from the ends is equivalent to leaving a contiguous middle block of length n - k.
  2. Maximising the taken score equals minimising the sum of the leftover middle block.
  3. So slide a window of length n - k across the array and find its minimum sum.
  4. The answer is total - min(window sum).

💻 Benchmark Python3 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               # take every card
        cur = sum(cardPoints[:window])
        best = cur
        for i in range(window, n):
            cur += cardPoints[i] - cardPoints[i - window]
            best = min(best, cur)
        return total - best

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n): one sliding pass after the prefix sum.
💾 Space Complexity
O(1): a few scalars.

⚠️ Interview Pitfalls & Follow-ups

  • Simulating greedy end-picking: a locally better end may not be globally optimal; the middle-window view is exact.
  • Forgetting k == n: then the window length is 0 and the answer is the total.
  • Maximising the window instead of minimising it: the window is the leftover, so it must be minimised.
  • Using a window of length k: the window is n - k.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Greedy Problems