Maximum Points You Can Obtain from Cards

There are several cards arranged in a row, and each card has an associated number of points The points are given in the integer array cardPoints.

In one step, you can take one card from the beginning or from the end of the row. You have to take exactly k cards.

Your score is the sum of the points of the cards you have taken.

Given the integer array cardPoints and the integer k, return the maximum score you can obtain.

 

Example 1:

Input: cardPoints = [1,2,3,4,5,6,1], k = 3
Output: 12
Explanation: After the first step, your score will always be 1. However, choosing the rightmost card first will maximize your total score. The optimal strategy is to take the three cards on the right, giving a final score of 1 + 6 + 5 = 12.

Example 2:

Input: cardPoints = [2,2,2], k = 2
Output: 4
Explanation: Regardless of which two cards you take, your score will always be 4.

Example 3:

Input: cardPoints = [9,7,7,9,7,7,9], k = 7
Output: 55
Explanation: You have to take all the cards. Your score is the sum of points of all cards.

Example 4:

Input: cardPoints = [1,1000,1], k = 1
Output: 1
Explanation: You cannot take the card in the middle. Your best score is 1. 

Example 5:

Input: cardPoints = [1,79,80,1,1,1,200,1], k = 3
Output: 202

 

Constraints:

• 1 <= cardPoints.length <= 10^5
• 1 <= cardPoints[i] <= 10^4
• 1 <= k <= cardPoints.length

Approach I (Minimum Sum Sub-Array Exclusion):

We can observe that at anytime, we are choosing some cards from left and right to maximize the score. Atlast, some subarray of cards (n - k in length) will remain. For the optimal answer, this remaining subarray must have minimum score (or sum). This will ensure that the set of chosen cards from left and right have the maximum score.

For this, we can iterate through the array and choose every subarray of length n - k and see if excluding this subarray will give us the maximum score. To do this efficiently, we will first calculate the first subarray sum (let's take it to be the leftmost subarray of length n - k). Every subsequent subarray sum will be calculated by subtracting the leftmost element and adding a new right element from the previous subarray.

The final answer will be total sum of array sum - the minimum subarray subArrSum.

C++ Code:

int maxScore(vector<int>& cp, int k) 
{
    int sum = accumulate(begin(cp), end(cp), 0);
    int subArrSum = accumulate(begin(cp), end(cp) - k, 0);
    int ans = sum - subArrSum;
    
    for(int r = cp.size() - k, l = 0; r < cp.size(); r++, l++)
        ans = max(ans, sum - (subArrSum += cp[r] - cp[l]));
    
    return ans;
}

Time Complexity : O(N), where N is the length of input array
Space Complexity : O(1), since only constant extra space is used.

Approach II (Two Pointers):

This solution is similar to solution - I but slightly optimized. Here, instead of finding minimum sum subarray and then subtracting it from total sum, we will just take the first take first k cards on the left and try to replace them one by one with cards on right end.

This solution will essentially try out every possible combination of taking k cards from the left and right end of the array. After each replacement from the right, we will only store the maximum of earlier score and score after replacement from the right end.

C++ Code:

int maxScore(vector<int>& cp, int k) {
    int sum = accumulate(begin(cp), begin(cp) + k, 0);
    int ans = sum;
    
    for(int l=(k-1), r=(cp.size() - 1); l >= 0; l--, r--)
        ans = max(ans, sum += (cp[r] - cp[l]));
    
    return ans;
}

Time Complexity : O(K), where K is the number of cards to be chosen. We only iterate over the first k cards (from the left) and last k cards (from the right). Thus, the final time complexity comes out to be O(2*K) = O(K)
Space Complexity : O(1), since only constant extra space is used.

💻🐱‍💻If there are any suggestions / questions / mistakes in my post, please do comment below 👇