LeetCode 1423 可获得最大点数
🟡 中等
正向
思考答案的各种情况之间的联系， 左边1， 右边k-1 ;左边2， 右边k-2， 他们之间是有联系的。
每次左边减一个， 右边加一个， 遍历完所有的情况。
class Solution {
public:
int maxScore(vector<int>& cardPoints, int k) {
int sum = 0;
int res = 0;
for(int i = 0;i<k;i++){
sum+=cardPoints[i];
}
res = sum;
int left = k-1;
int right = cardPoints.size()-1;
for(int i = 0;i<k;i++){
sum-=cardPoints[left];
sum+=cardPoints[right];
res = max(res,sum);
left--;
right--;
}
return res;
}
};
逆向
可以看成滑动窗口， 两侧的最大就是中间的最大. 因此可以使用定长滑动窗口找到最小的窗口， 剩下的就是最大的答案。