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
- Taking
kcards from the ends is equivalent to leaving a contiguous middle block of lengthn - k. - Maximising the taken score equals minimising the sum of the leftover middle block.
- So slide a window of length
n - kacross the array and find its minimum sum. - 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 isn - k.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.