1423. 可获得的最大点数 Medium
几张卡牌 排成一行，每张卡牌都有一个对应的点数。点数由整数数组 cardPoints 给出。
每次行动，你可以从行的开头或者末尾拿一张卡牌，最终你必须正好拿 k 张卡牌。
你的点数就是你拿到手中的所有卡牌的点数之和。
给你一个整数数组 cardPoints 和整数 k，请你返回可以获得的最大点数。
示例 1：
输入：cardPoints = [1,2,3,4,5,6,1], k = 3
输出：12
解释：第一次行动，不管拿哪张牌，你的点数总是 1 。但是，先拿最右边的卡牌将会最大化你的可获得点数。最优策略是拿右边的三张牌，最终点数为 1 + 6 + 5 = 12 。
示例 2：
输入：cardPoints = [2,2,2], k = 2
输出：4
解释：无论你拿起哪两张卡牌，可获得的点数总是 4 。
示例 3：
输入：cardPoints = [9,7,7,9,7,7,9], k = 7
输出：55.
解释：你必须拿起所有卡牌，可以获得的点数为所有卡牌的点数之和。
示例 4：
输入：cardPoints = [1,1000,1], k = 1
输出：1
解释：你无法拿到中间那张卡牌，所以可以获得的最大点数为 1 。
示例 5：
输入：cardPoints = [1,79,80,1,1,1,200,1], k = 3
输出：202
解题思路
输入：一个整数数组 cardPoints，一个整数 k
输出：返回可以获得的最大点数
本题属于固定长度滑动窗口类型问题。
- 数组长度为 n，我们要取 k 张牌，相当于保留中间连续的
n-k张牌不要。 - 我们可以将这道题转化成：在
cardPoints中找出和最小的连续n-k子数组，剩下的就是我们取的部分了，最大得分就是sum(cardPoints) - minSubarraySum(n - k)。
代码实现
python
class Solution:
def maxScore(self, cardPoints: List[int], k: int) -> int:
n = len(cardPoints)
total = sum(cardPoints) # 先算出所有卡牌的总分数
# 如果k等于卡牌总数，直接全部拿走
if k == n:
return total
# 我们等价于从中间保留 n - k 张牌，找它们中和最小的部分
window_size = n - k
# 先计算第一个长度为 window_size 的子数组的和
window_sum = sum(cardPoints[:window_size])
min_subarray_sum = window_sum # 初始化为第一个窗口的和
# 用滑动窗口向右滑，找最小的连续 n - k 子数组之和
for i in range(window_size, n):
# 滑动窗口更新：加上右边元素，减去左边元素
window_sum += cardPoints[i] - cardPoints[i - window_size]
# 记录当前最小值
min_subarray_sum = min(min_subarray_sum, window_sum)
# 最大得分 = 总和 - 中间最小子数组和
return total - min_subarray_sumjavascript
/**
* @param {number[]} cardPoints
* @param {number} k
* @return {number}
*/
var maxScore = function(cardPoints, k) {
const total = cardPoints.reduce((acc, curr) => acc + curr, 0);
if (cardPoints.length === k) return total;
const windowSize = cardPoints.length - k;
let windowSum = 0
for (let i = 0; i < windowSize; i++) {
windowSum += cardPoints[i];
}
let minWindowSum = windowSum;
for (let j = windowSize; j < cardPoints.length; j++) {
windowSum += cardPoints[j] - cardPoints[j - windowSize];
minWindowSum = Math.min(minWindowSum, windowSum);
}
return total - minWindowSum;
};复杂度分析
时间复杂度：O(n)
空间复杂度：O(1)