可获得的最大点数（1423）

题目

几张卡牌 排成一行，每张卡牌都有一个对应的点数。点数由整数数组 cardPoints 给出。

每次行动，你可以从行的开头或者末尾拿一张卡牌，最终你必须正好拿 k 张卡牌。

你的点数就是你拿到手中的所有卡牌的点数之和。

给你一个整数数组 cardPoints 和整数 k，请你返回可以获得的最大点数。

示例

输入：cardPoints = [1,2,3,4,5,6,1], k = 3 输出：12

解释：第一次行动，不管拿哪张牌，你的点数总是 1 。但是，先拿最右边的卡牌将会最大化你的可获得点数。最优策略是拿右边的三张牌，最终点数为 1 + 6 + 5 = 12 。

输入：cardPoints = [2,2,2], k = 2 输出：4

解释：无论你拿起哪两张卡牌，可获得的点数总是 4 。

输入：cardPoints = [9,7,7,9,7,7,9], k = 7 输出：55

解释：你必须拿起所有卡牌，可以获得的点数为所有卡牌的点数之和。

输入：cardPoints = [1,1000,1], k = 1 输出：1

解释：你无法拿到中间那张卡牌，所以可以获得的最大点数为 1 。

输入：cardPoints = [1,79,80,1,1,1,200,1], k = 3 输出：202

提示

• 1 <= cardPoints.length <= 10^5
• 1 <= cardPoints[i] <= 10^4
• 1 <= k <= cardPoints.length

算法

动态规划

使用两个数组fromLeft和fromRight分别保存从左拿i张牌和从右拿i张牌的的点数值和，fromLeft[0] = fromRight[0] = 0，即从两边取0张牌点数为0

然后我们从左边取i张牌，从右遍取j张牌，且i + j === k，即此时点数为fromLeft[i] + fromRight[j]

我们使用变量maxPoints每次点数的最大值，最后结果返回maxPoint

export const maxScore = (cardPoints, k) => {
	const fromLeft = [0];
	const fromRight = [0];
	for (let i = 0; i < k; i++) {
		fromLeft.push(cardPoints[i] + fromLeft[i]);
		fromRight.push(cardPoints[cardPoints.length - 1 - i] + fromRight[i]);
	}
	let maxPoints = -Infinity;
	let j = k;
	while (j >= 0) {
		const curPoints = fromLeft[j] + fromRight[k - j];
		j--;
		maxPoints = Math.max(maxPoints, curPoints);
	}
	return maxPoints;
};

滑动窗口

因为是从左或从右连续取牌，我们将中间不需要取得牌放在一个滑动窗口中，用总点数减去滑动窗口中的点数就是手中的点数

如果我们每滑动依次窗口就计算一次窗口中的值，当数据量很大时就会超时

所以我们先将窗口在最左侧的情况求出窗口中的值，放入变量windowSum，然后我们每滑动一次窗口，减去左侧划出窗口的值，加上右侧滑入窗口的值，就得到了新窗口的值

使用变量max保存每一次得最大值，最后结果返回max即可

export const maxScore = (cardPoints, k) => {
	let sum = 0;
	let windowSum = 0;
	for (let i = 0, j = 0; i < cardPoints.length; i++, j++) {
		sum += cardPoints[i];
		if (j < cardPoints.length - k) windowSum += cardPoints[i];
	}
	let max = sum - windowSum;
	for (let i = 0; i < k; i++) {
		windowSum -= cardPoints[i];
		windowSum += cardPoints[cardPoints.length - k + i];
		max = Math.max(max, sum - windowSum);
	}
	return max;
};