DAY 31 - Maximum Points You Can Obtain from Cards

Hey Guys! Nayan here and this is the 31st day of the 100-DAY challenge. If you are reading this for the first time , I learn and solve some questions throughout the day and post them here. I may be incorrect many times and might be following a bad practice, Please feel free to correct me or advise me at any point.

Question 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.

Examples :

• 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.

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

Intuition:

Let's break down the question first as usual.
We can either select the 0th index element or the element at the last index of array.
We can do it at most K times and we have to do it such that the sum is maximum.

At the start it looks like a DP problem. Pick the first element or pick the last element. Return max of all cases.
Although it can be solved using DP, it will require us to use extra space.
We can do it optimally using the sliding window method.

Although it's not visible directly this is a sliding window problem.

Let's see all our cases on one example and see if we can see the pattern here.

This is a sliding window. With its head on the 0th index and going towards n-kth index from reverse and it's tail at kth index and shrinking towards 0th index.

Another way to think of this problem is, Whenever we choose 3 elements, there is a subarray of size n-k left. If we can minimize that subarray we can subtract it from total sum to return our answer.

I think this is enough to understand it, It's more of a visualization kinda problem than basic pattern application here. Hence making it a good problem.

Approach:

1. Initialize a variable res to 0. This variable will store the maximum score.

2. Iterate i from 0 to k-1 using a for loop. In each iteration, add the value of cardPoints[i] to res. This step calculates the total score by considering the first K cards.

3. Initialize a variable curr to the value of res. So that we can maintain current value.

4. Start a for loop from k-1 down to 0 (inclusive) with a step size of -1.

5. In each iteration, subtract the value of cardPoints[i] (the current card being removed) from curr.

6. Add the value of cardPoints[cardPoints.size()-k+i] to curr. This step effectively simulates removing the current card from the front and adding a new card from the back.

7. Update res to the maximum value between res and curr.

8. After the loop finishes, res will contain the maximum score that can be obtained by selecting k cards from the given cardPoints vector.

Code:

int maxScore(vector<int>& cardPoints, int k) {
        int res = 0;
        for(int i = 0; i < k; i++) res+= cardPoints[i];
        int curr = res;
        for(int i = k-1; i >=0; i--){
            curr -=cardPoints[i];
            curr += cardPoints[cardPoints.size()-k+i];
            res = max(res, curr);
        }

        return res;
    }

Complexity Analysis:

Time Complexity: O(N)
Space Complexity: O(1). where N is the size of cardPoints.

In summary, the code uses a sliding window approach to find the maximum score by removing cards from the front and adding cards from the back of the vector. It keeps track of the current score and updates the maximum score whenever a higher score is found.

Thanks for reading. Feedback is highly appreciated.