Leetcode 1423. 可获得的最大点数 （正向记忆话搜索超时，逆向思维滑动窗口）

正向记忆话搜索代码

class Solution {
public:
    int maxScore(vector<int>& cardPoints, int k) {
        // dp[i][j] 表示区间i到j抽取的最大点数
        int n = cardPoints.size();
        vector<vector<int>> dp(n,vector<int>(n));
        return dfs(dp,cardPoints,0,n-1,k);
    }

    int dfs(vector<vector<int>> &dp, vector<int> & cardPoints, int i, int j, int k){
        if(k==0) return 0;
        if(dp[i][j]!=0) return dp[i][j];
        int left = dfs(dp,cardPoints,i+1,j,k-1) + cardPoints[i];
        int right = dfs(dp,cardPoints,i,j-1,k-1) + cardPoints[j];
        dp[i][j] = max(left,right);
        return dp[i][j];
    }
};

这道题目要逆向思维，从前面和后面抽出来的最大和等于总的最大和-中间部分最小和，所以问题就转化为找到n-k滑动窗口中的最小值，时间可以优化到O(N)

class Solution {
public:
    int maxScore(vector<int>& cardPoints, int k) {
        // 逆向思维，等价于n-k个元素的最大值。
        int n = cardPoints.size();
        int m = n-k, sum = 0, res = INT_MAX, total_sum = 0;
        for(int i=0;i<n;i++) {
            total_sum+=cardPoints[i];
            if(i<m){
                sum+=cardPoints[i];
            }
        }
        res = sum;
        for(int i=m;i<n;i++){
            sum += (cardPoints[i]-cardPoints[i-m]);
            res = min(res,sum);
        }
        return total_sum-res;
    }
};