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.

Give a set of cards , Only one at a time can be drawn from the beginning or the end , A total of k Zhang ,
Add up the points of the drawn cards , Ask the maximum number of points you can reach .

Ideas ：

Easily confused by the concept of draw order , For example, whether to draw the tail first or draw the tail first ,
In fact, the concept of draw order can be ignored , Just think ： First draw a few , Draw a few at the end . Because there is always order to achieve .

For example, I want a head 2 Zhang , The last one , It can be realized by the sequence of beginning, ending and beginning .
head 1 Zhang , Last two , You can use the tail , head , The tail is realized in this order .

So the problem becomes how many numbers are taken from the head of the array , Take a few numbers from the tail , To maximize the sum .

Then use the sliding window method , First take the array header k A digital , This is a window , Then remove a number from the right side of the window in turn , Replace it with a number at the end of the array ,
Until the array header 0 A digital , The tail k A number .
Record the largest sum in the process .

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;
}

Reference link