1、前言

2、思路
逆向思维:求拿走的最大值,不如先求剩下牌的最小值,然后用总和减去最小值,就是最大值了。
只需要设置一个 n-k 大的滑动窗口,不停的从头到尾开始滑动就行
3、代码
递归:
public int maxScore(int[] cardPoints, int k) {
int n = cardPoints.length;
Map<Integer, Integer> map = new HashMap<>();
return dfs(cardPoints, map, k, 0, n - 1, n);
}
private int dfs(int[] cardPoints, Map<Integer, Integer> map, int k, int left, int right, int n){
if(k == 0){
return 0;
}
int posi = left * n + right;
if(map.containsKey(posi)){
return map.get(posi);
}
int leftSum = cardPoints[left] + dfs(cardPoints, map, k - 1, left + 1, right, n);
int rightSum = cardPoints[right] + dfs(cardPoints, map, k - 1, left, right - 1, n);
int max = Math.max(leftSum, rightSum);
map.put(posi, max);
return max;
}
滑动窗口
class Solution {
public int maxScore(int[] cardPoints, int k) {
int n = cardPoints.length;
int windowSize = n - k, sum = 0;
for(int i = 0; i < windowSize; i++){
sum += cardPoints[i];
}
int min = sum;
for(int i = windowSize; i < n; i++){
sum = sum + cardPoints[i] - cardPoints[i - windowSize];
min = Math.min(min, sum);
}
return Arrays.stream(cardPoints).sum() - min;
}
}
网友评论