解题思路

算法1 （正向）

1. 首先这道题用前缀和，前缀和——任意区间数组和均可以使用前缀和来优化
2. 因为始终都是从两端抽牌，我们可以从枚举从左端抽和从右端抽。从左端抽牌的结果就是s[j]，j从0开始枚举，到k结束。因为一共只抽k张牌，所以从右端抽牌的数量对应就是k - j(对应j = 0)，到k - j(对应j = k)。
3. 对应到代码，从左端抽牌的结果是s[j]，从右端的结果是s[n] - s[n - (k - i)](这里不懂，建议在纸上画一画，理解一下前缀和hh)，j从0开始枚举，到k结束，二者加起来就是答案res了。

代码_算法1

class Solution {
public:
    int maxScore(vector<int>& ca, int k) {
        int n = ca.size();
        vector<int> s(n + 1);

        for(int i = 0; i < n; i ++) s[i + 1] = s[i] + ca[i];

        int res = 0;
        for(int j = 0; j <= k; j ++) res = max(res, s[j] + (s[n] - s[n - (k - j)]));

        return res;
    }
};

以下这个算法是一个清华大佬提出的

算法2 （反向）

1. 因为总和是不变的，所以求k的最大值，就是求n - k的最小值
2. 选两端的k个 剩下的就是中间的连续n-k个
3. 只需要找到n-k个数的和最小是多少
4. 然后用全部的和sum减去它，就是答案了
5. 这里最终的枚举逻辑：
   • s[n - k] - s[0] 表示选的都是左端3个，右端1个都没选。
   • s[n - k + 1] - s[1] 表示选的都是左端2个，右端选了1个。
   • …
   • s[n - k + k] - s[k] 表示选的都是右端3个，左端1个都没选。
6. 一开始，从左端选了0个，右端选了k个开始枚举, s[n - k + 0] - s[0]。然后，左端加1的时候，s[n - k + 1]，然后再减一个s[1]，左端加2的时候，s[n - k + 2]，然后再减一个s[2]，…，左端加k的时候，s[n - k + k]，然后再减一个s[k]，

class Solution {
public:
    int maxScore(vector<int>& ca, int k) {

        int n = ca.size();
        int t = n - k;

        vector<int> s(n + 1);

        for(int i = 0; i < n; i ++) s[i + 1] = s[i] + ca[i];
        int len = s.size();

        int ans = 0x3f3f3f3f;
        for(int j = t; j <= n; j ++) ans = min(ans, s[j] - s[j - t]);
        // for(int j = t; j < len; j ++) ans = min(ans, s[j] - s[j - t]);  写成这个语句也可以过，区间得开成闭区间

        return s[n] - ans;
    }
};