# 1423. 可获得的最大点数
# 题目
几张卡牌 排成一行，每张卡牌都有一个对应的点数。点数由整数数组 cardPoints 给出。
每次行动，你可以从行的开头或者末尾拿一张卡牌，最终你必须正好拿 k 张卡牌。
你的点数就是你拿到手中的所有卡牌的点数之和。
给你一个整数数组 cardPoints 和整数 k，请你返回可以获得的最大点数。
例
输入：cardPoints = [1,2,3,4,5,6,1], k = 3
输出：12
解释：第一次行动，不管拿哪张牌，你的点数总是 1 。但是，先拿最右边的卡牌将会最大化你的可获得点数。最优策略是拿右边的三张牌，最终点数为 1 + 6 + 5 = 12 。
# 题解
# 滑动窗口
只能左右边上拿卡，反过来思考，拿到最大的值代表剩下的卡是最小的值，也就是求连续 len-k 长度的子数组的最小值，然后用数组总和减去该值
/**
* @param {number[]} cardPoints
* @param {number} k
* @return {number}
*/
var maxScore = function(cardPoints, k) {
let windowSize = cardPoints.length - k;
let sum = 0;
for (let i = 0; i < windowSize; ++i) {
sum += cardPoints[i];
}
let minSum = sum;
for (let i = windowSize; i < cardPoints.length; ++i) {
sum = sum - cardPoints[i - windowSize] + cardPoints[i];
minSum = Math.min(sum, minSum);
}
let totalSum = 0;
for (let i = 0; i < cardPoints.length; ++i) {
totalSum += cardPoints[i];
}
return totalSum - minSum;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
时间复杂度：O(n)
空间复杂度：O(1)