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.

My Solutions:

牌只能从两边拿。因此，先在左边拿到所有k张牌，记录一个window值。然后做一个sliding window，每次从右边拿一张，就减去左边的k张牌里最右边的拿一张。直到所有的k张牌都是牌堆最右边的牌。在这个移动sliding window的过程中，不断更新最大值。

class Solution {
    public int maxScore(int[] cardPoints, int k) {
        int window = 0;
        // make a window, which starts from index=0 and ends at index=k-1, with length = k
        for (int i = 0; i < k; i++) {
            window += cardPoints[i];
        }
        if (k == cardPoints.length) return window;
        
        // when we delete an element from the end of the window, we add an element from the end the cards
        int max = window;
        int endOfCards = cardPoints.length - 1; // end of the cards
        int endOfWindow = k - 1; // end of the current window
        while (endOfWindow >= 0) { // loop until the endOfWindow does not contain the first element in the original window anymore
            window += cardPoints[endOfCards--]; 
            window -= cardPoints[endOfWindow--];
            max = Math.max(max, window); // keep the max of sum
        }
        return max;    
    }
}