leetcode 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.

给一组牌，每次只能从头或尾抽一张，一共要抽k张，
把抽到的牌的点数加起来，问能达到的最大点数和是多少。

思路：

容易被抽牌顺序这个概念迷惑，比如是先抽头还是先抽尾呢，
其实可以忽略抽牌顺序这个概念，直接就想：头抽几张，尾抽几张。因为总有顺序能实现。

比如我想要头2张，尾一张，可以通过先头再尾再头这样的顺序实现。
头1张，尾两张，可通过尾，头，尾这样的顺序实现。

于是问题变成了数组头部取几个数字，尾部取几个数字，才能使和最大。

那么用滑动窗口的方法，首先取数组头部k个数字，这是一个窗口，然后依次从窗口右边去掉一个数字，换作数组尾部的一个数字，
直到数组头部0个数字，尾部k个数字为止。
记录下这个过程中最大的和。

public int maxScore(int[] cardPoints, int k) {
    int res = 0;
    int i = 0;
    int sum = 0;
    int n = cardPoints.length;
    
    while(i < k) {
        sum += cardPoints[i];
        i ++;
    }
    
    i = k - 1;
    res = sum;
    
    while(i >= 0) {
        sum = sum - cardPoints[i] + cardPoints[n - k + i];
        res = Math.max(res, sum);
        i --;
    }
    return res;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

参考链接