1423. Maximum Points You Can Obtain From Cards

/**

 * 1423. 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.

 *

 * 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

*/

See the solution I am describing below on github at: https://github.com/zcoderz/leetcode/blob/main/src/main/java/google/medium/MaximumCardPointsFast.java

See another recursive memorization-based solution on github at: https://github.com/zcoderz/leetcode/blob/main/src/main/java/google/medium/MaximumCardPoints.java

Observation: You are being asked to find the maximum points of cards by picking cards from either left or right of the array until you reach the desired number of cards. You can think of the left and right sides of the array as connected and then calculate the maximum via sliding window of all K on the right end to all K on the left. Or you can calculate minimum of first len-K and then move one to right until you reach the end to calculate the minimum contiguous span of len-K. The max then be total sum – minimum contiguous sum of len-K. I describe this approach below.

Logic:

1. Find total sum of the array
2. First sum of first length -K elements
   1. Iterate to right via sliding window approach
   1. Track minimum per index as you iterate right in a variable
3. The answer being requested (max possible sum of K from either left or right) is simply 1 – 2b.

Here is the code:

public int maxScore(int[] cardPoints, int k) {
    int len = cardPoints.length;
    int totalScore = 0;
    for (int i =0; i < cardPoints.length; i++) {
        totalScore += cardPoints[i];
    }
    int leftOvers = len-k;
    int sum = 0;
    int i =0;
    for ( ; i < leftOvers; i++) {
        sum += cardPoints[i];
    }
    int min = sum;
    while (i < len) {
        sum += cardPoints[i];
        sum -= cardPoints[i-leftOvers];
        i++;
        min = Math.min(sum, min);
    }
    return totalScore - min;
}