leetcode 1423. 可获得的最大点数

1423. 可获得的最大点数

首先，前 k 个数和后 k 个数 的 较大者并不是正确答案，比如  100   40   17   9   73   75，正确解是248。

其次，想到了前或者后拿了一个数之后，就是求剩下序列拿k-1个数，可以转换成子问题，所以想到了递归。但是k比较大的时候就超时了：

class Solution {
public:
    int maxScore_2(const vector<int>& cardPoints, const int& k, const int& left,const int& right){
        if(k == 0)  return 0;
        if(left == right)  return cardPoints[left];
        int sumLeft = cardPoints[left] + maxScore_2(cardPoints,k-1,left+1,right);
        int sumRight = cardPoints[right] + maxScore_2(cardPoints,k-1,left,right-1);
        return max(sumLeft,sumRight);
    }

    int maxScore(vector<int>& cardPoints, int k) {
        return maxScore_2(cardPoints,k,0,cardPoints.size()-1);
    }
};