Leetcode: Maximum Points You Can Obtain from Cards

 

This question is commonly asked at Google and Flipkart and it is as follows:

There are several cards arranged in a row, and each card has an associated number of points, and the points are given in the integer array, cardpoints. In one step you can take one card from the beginning or the end of the row, and you need to take exactly k cards and you want to have the maximum score you can obtain given the integer array cardPoints and the integer K.

Here are the examples:

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

And here are the hints: 

Let the sum of all points be total_pts. You need to remove a sub-array from cardPoints with length n - k.

Keep a window of size n - k over the array. The answer is max(answer, total_pts - sumOfCurrentWindow)

Now, let's get to solving the problem. There's a sliding window case here, but right now, I will go through the dynamic programming instance of this problem. 

We should first have a dynamic programming array representing the total number of points when taking a specific number of cards from the left. I have taken this array and a given case 3 for the array of [5,3,4,8,1]. The approach first here is taking the maximum of first and last element and store it in sum and wait until I take k elements. This fails because the sum will be 12, or 5,3,4 which isn't the maximum sum. We should do 5 + 1 + 8, which would equal to 14 sumwise.

We would take a left_sum, which is the sum from the left, and a right_sum, which is the sum from the right. The left sum array we store k + 1 elements as 0, 5, 8, 12 as 0, 5 + 3, 5 + 3 + 4. We do the same for the right array and get 0, 1, 9, 13 (0 + 1 + 8 + 4).

We take the maximum sum of 2 different elements, the n with the k - nth element or the nth with the nth last element and maximize this.

Here's the solution: 

class Solution {

    public int maxScore(int[] cardPoints, int k) {

        //left and right array sums

        int[]  left_sum = new int[k + 1];

        int[] right_sum = new int[k + 1];

         //sum both the left array and right array from both sides

        for(int i = 1; i <= k; i++) {

            left_sum[i] = left_sum[i - 1] + cardPoints[i - 1];

            right_sum[i] = right_sum[i - 1] + cardPoints[cardPoints.length - i];

        }

        //take the maximum of the sum of the nth and nth last elements

        int sum = 0;

        for(int i = 0; i <= k; i++) {

            sum = Math.max(sum, left_sum[i] + right_sum[k - i]);

        }

        //return the sum.

        return sum;

    }

}