DAY 31 - Maximum Points You Can Obtain from Cards
Tags: coding, codenewbie, leetcode, tutorial
Published: 2023-07-04 17:23:35

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.


![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/hvjp1af07witmtrrc8p7.png)

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.