几张卡牌 排成一行，每张卡牌都有一个对应的点数。点数由整数数组 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
提示：
1 <= cardPoints.length <= 10^51 <= cardPoints[i] <= 10^41 <= k <= cardPoints.length
题解
上手直接开始想象下，k次取牌，那么这k张牌可以分为两个部分，从左边取的left张，和从右边取的right张，且left+right = k
那么接下来就是挨个情况求和，然后求出一个最大值了，假设求得的合为sum,左边求得的合为sum_left，右边求得的合为sum_right，就有sum = sum_left + sum_right。
那么分别分情况来，假设left是每次减一个位置，right是每次加一个位置
第一次，左边left_1个的时候，右边对应right_1个有sum_1 = sum_left_1 + sum_right_1
第二次，左边left_2个的时候，右边对应right_2个有sum_2 = sum_left_2 + sum_right_2
第三次，哦，不是，这时候我们可以看到sum_left_2 = sum_left_1 – 第left_1位的值，sum_right_2 = sum_right_1 + 第right_2位的值
这样基本的模式就可以看出来了，就是窗口模式，如果还没明白的话，试想着将cardPoints 数组首位相连，连接成一个环状，这样是不是就显而易见了。
直接上代码
import java.util.Arrays;
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
public int maxScore(int[] cardPoints, int k) {
int maxSum = 0;
//左边全选拉满来一次作为基本值
for (int i = 0; i < cardPoints.length && i < k; i++) {
maxSum += cardPoints[i];
}
if (k >= cardPoints.length){
//如果k的值比cardPoints长度长，或者等于长度
return maxSum;
}
//此时左边取了k个，右边取了0个
//那么继续滑动窗口左边减一个，右边加一个
int lastSum = maxSum;
for (int right = 1; right <= k; right++) {
lastSum = lastSum - cardPoints[k-right] + cardPoints[cardPoints.length-1-(right-1)];
maxSum = Math.max(maxSum, lastSum);
}
return maxSum;
}
}既然我们已经用了滑动窗口，那么不妨可以再回来看下这个数组
除去头和尾巴的两段连起来做滑动窗口，其实可以把中间没有选择的cardPoints.length-k张牌作为另一个滑动窗口来看待，那么相对的，就是要求这个滑动窗口取得最大值的时候，再拿所有合减去这个最大的值就是所求目标值
逻辑基本相同的代码省略
发表评论