原题地址（中等）

方法1—滑动窗口

思路

官方用的滑动窗口，很妙。

代码

  1. class Solution {
  2. public:
  3.     int maxScore(vector<int>& cardPoints, int k) {
  4.         int n = cardPoints.size();
  5.         // 滑动窗口大小为 n-k
  6.         int windowSize = n - k;
  7.         // 选前 n-k 个作为初始值
  8.         int sum = accumulate(cardPoints.begin(), cardPoints.begin() + windowSize, 0);
  9.         int minSum = sum;
  10.         for (int i = windowSize; i < n; ++i) {
  11.             // 滑动窗口每向右移动一格，增加从右侧进入窗口的元素值，并减少从左侧离开窗口的元素值
  12.             sum += cardPoints[i] - cardPoints[i - windowSize];
  13.             minSum = min(minSum, sum);
  14.         }
  15.         return accumulate(cardPoints.begin(), cardPoints.end(), 0) - minSum;
  16.     }
  17. };
  19. 作者：LeetCode-Solution
  20. 链接：https://leetcode-cn.com/problems/maximum-points-you-can-obtain-from-cards/solution/ke-huo-de-de-zui-da-dian-shu-by-leetcode-7je9/
  21. 来源：力扣（LeetCode）
  22. 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

时空复杂度

时间复杂度O(N) 空间复杂度O(1)

方法2—前缀后缀和

思路

虽然滑动窗口很妙，但是我也有自己的想法。
我的题解：

代码

  1. class Solution {
  2. public:
  3.     int maxScore(vector<int>& cardPoints, int k) {
  4.         int n = cardPoints.size();
  5.         vector<int> left(n, 0), right(n, 0);
  6.         // 计算left
  7.         for(int i = 0; i < n; i++) {
  8.             if(i > 0)   left[i] = left[i-1] + cardPoints[i];
  9.             else    left[i] = cardPoints[i];
  10.         }
  11.         // 计算right
  12.         for(int i = n - 1; i >= 0; i--) {
  13.             if(i == n -  1)     right[i] = cardPoints[i];
  14.             else    right[i] = right[i+1] + cardPoints[i];
  15.         }
  16.         // 遍历尝试
  17.         int ans = 0;
  18.         for(int i = 0; i <= k; i++) {
  19.             if(i == 0)  ans = max(ans, right[n-k]);
  20.             else if(i == k) ans = max(ans, left[k-1]);
  21.             else    ans = max(ans, left[i-1] + right[n-k+i]);
  22.         }
  23.         return ans;
  24.     }
  25. };

时空复杂度

时间复杂度O(N) 空间复杂度O(N)