Leetcode #1423: Maximum Points You Can Obtain from Cards

Link to the Problem

Maximum Points You Can Obtain from Cards

Thought Process

You can’t choose the 2^nd element from the front unless you have chosen the first one. Similarly, you can’t choose the 2^nd element from the back unless you have chosen the last one already. So in general, you can not directly select some number from the array at random. You will have to select all the numbers before or after that element in order to select that number. This makes the problem easy.

You want to choose a total of K numbers. There are limited number of ways in which you can choose those numbers given the constraints. One way is to choose all K numbers from the front and no number from the back. Another way is to choose K-1 numbers from the front and 1 number from the back. Similarly, K-2 number from the front and 2 from the back, and so on. Finally, no numbers from the front and K numbers from the back. At the end simply find the best way.

Leetcode #1423: Maximum Points You Can Obtain from Cards - Leetcode Solutions - Problem Solving — Leetcode #1423: Maximum Points You Can Obtain from Cards – Diagram to assist visualization

Algorithm

Find cumulative sum from the front to every index i.
Find cumulative sum from the back to every index i.
If you choose i elements from front, you will need to choose k-i elements from behind.
Sum of first i elements = cumulativeSumFromFront[i],
Sum of last (k-i) elements = cumulativeSumFromBehind[K-i].
So points obtained when choosing i elements from the front = cumulativeSumFromFront[i] + cumulativeSumFromBehind[K-i].
Repeat the Step 3 for all i ranging from 0 to K.
Return the maximum value of points reached.

Code

      
        class Solution {
      
        public:
      
            int maxScore(vector<int>& cardPoints, int k) {
      
                int n = cardPoints.size();
      
                vector<int> cumulativeSumFront(n+1, 0); // For easier indexing, add an extra element.
      
                vector<int> cumulativeSumBack(n+1, 0);  // For easier indexing, add an extra element.
      
                for (int i=0; i<n; i++) {
      
                    cumulativeSumFront[i+1] = cumulativeSumFront[i] + cardPoints[i];
      
                }
      
                for (int i=n-1; i>=0; i--) {
      
                    cumulativeSumBack[i] = cumulativeSumBack[i+1] + cardPoints[i];
      
                }
      
                // Reversing is optional. I reversed it so that it would be easy
      
                // to access sum of last (k-i) elements by just indexing at [k-i]
      
                // Otherwise, I would have had to index it at [n-k+i] which would
      
                // have made it difficult to read.
      
                reverse(cumulativeSumBack.begin(), cumulativeSumBack.end());
      
                int answer = 0;
      
                for(int i=0; i<=k; i++) {   
      
                    answer = max(answer, 
      
                                   cumulativeSumFront[i] // Sum of 'i' cards from the front.
      
                                 + cumulativeSumBack[k-i]); // Sum of 'k-i' cards from the back.
      
                }
      
                return answer;
      
            }
      
        };

view raw Leetcode_1423.cpp hosted with ❤ by GitHub

Another Way to visualize this is as a sliding window.

Is there anything that is still unclear? Let me know in the comments and I can elaborate further.

Don’t forget like & share the post, and subscribe to the blog to get notifications whenever solution to a new problem is added.

Happy Coding!

Crack Every Coding Interview

Here is how you can crack your coding interview every single time