Maximum Points You Can Obtain from Cards [Medium] — Complement Window
Sanjeev SharmaAdvertisement
Problem Statement
From an array of card values, pick exactly k cards from either end. Maximize the total points.
Input: cardPoints=[1,2,3,4,5,6,1], k=3 → Output: 12 ([1,6,5] from ends)
Intuition
Total sum minus minimum sum of middle n-k consecutive cards. Use fixed window of size n-k, find minimum window sum.
Solutions
C++
int maxScore(vector<int>& cardPoints, int k) {
int n=cardPoints.size(), wSize=n-k;
int wSum=0;
for(int i=0;i<wSize;i++) wSum+=cardPoints[i];
int minWin=wSum, total=accumulate(cardPoints.begin(),cardPoints.end(),0);
for(int i=wSize;i<n;i++){
wSum+=cardPoints[i]-cardPoints[i-wSize];
minWin=min(minWin,wSum);
}
return total-minWin;
}
Java
public int maxScore(int[] cardPoints, int k) {
int n=cardPoints.length, wSize=n-k, total=0, wSum=0;
for(int x:cardPoints) total+=x;
for(int i=0;i<wSize;i++) wSum+=cardPoints[i];
int minWin=wSum;
for(int i=wSize;i<n;i++){wSum+=cardPoints[i]-cardPoints[i-wSize];minWin=Math.min(minWin,wSum);}
return total-minWin;
}
Python
def maxScore(cardPoints: list[int], k: int) -> int:
n, w = len(cardPoints), len(cardPoints)-k
win = sum(cardPoints[:w])
min_win = win
for i in range(w, n):
win += cardPoints[i] - cardPoints[i-w]
min_win = min(min_win, win)
return sum(cardPoints) - min_win
Complexity
- Time: O(n), Space: O(1)
Advertisement
