力扣1423.卡牌的最大点数

力扣1423.卡牌的最大点数

逆向做法 O(n)

• 最终没取到的卡片一定是一个连续的数组 长度为n-k

  • 即求长度为n-k的区间的最小值

•   class Solution {public:int maxScore(vector<int>& cardPoints, int k) {int n = cardPoints.size();int m = n-k;int sum = accumulate(cardPoints.begin(),cardPoints.begin()+m,0);int res = sum;int add = accumulate(cardPoints.begin(),cardPoints.end(),0);for(int i=m;i<n;i++){sum += cardPoints[i] - cardPoints[i-m];res = min(res,sum);}return add - res;}};
  

正向做法 O(k)

• 预处理前k个数的和

  • 每次处理将第k-i-1个数删去 加上末尾的第n-i个

•   class Solution {public:int maxScore(vector<int>& cardPoints, int k) {int sum = 0, ans = 0;  int n = cardPoints.size()-1;sum = ans = accumulate(cardPoints.begin(),cardPoints.begin()+k,0);for(int i=0;i<k;i++){sum += cardPoints[n-i] - cardPoints[k-i-1];ans = max(ans,sum);}return ans;}};