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 2nd element from the front unless you have chosen the first one. Similarly, you can’t choose the 2nd 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

  1. Find cumulative sum from the front to every index i.
  2. Find cumulative sum from the back to every index i.
  3. 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].
  4. Repeat the Step 3 for all i ranging from 0 to K.
  5. 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.

Leetcode #1423: Maximum Points You Can Obtain from Cards - Leetcode Solutions - Problem Solving
Leetcode #1423: Maximum Points You Can Obtain from Cards – Sliding Window Visualization

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!

Similar Problems

Leetcode #303: Range Sum Query – Immutable
Leetcode #523: Continuous Subarray Sum
Leetcode #209: Minimum Size Subarray Sum



Related Posts


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s