【Leetcode Daily】1423可获得的最大点数

题目浅析

• 想查看原题可以点击题目链接。

• 简单地说，就是给一个整型数组和一个数字 k，求按照某种方式下获取卡牌所得的最大点数。该方式为每次只能够取得最左或者最右的卡牌。

思路分享

• 逆向思路，由于每次拿卡牌只拿两侧，所以中间部分是连续的，可以视为一个定长滑动窗口，只不过是求窗口内的最小和，通过这个数值得到答案。滑动窗口模板沿用【Leetcode Daily】1456定长子串中元音的最大数目

• 正向思路，穷举所有组合可能。

  https://leetcode.cn/problems/maximum-points-you-can-obtain-from-cards/solutions/2551432/liang-chong-fang-fa-ni-xiang-si-wei-zhen-e3gb/

代码解答（强烈建议自行解答后再看）

• 逆向

class Solution {
public:
    int maxScore(vector<int>& cardPoints, int k) {
        cout << reduce(cardPoints.begin(), cardPoints.begin()) << endl;
        int win_size = cardPoints.size() - k;
        if (win_size == 0) return reduce(cardPoints.begin(), cardPoints.end());

        int min_sum = INT_MAX;
        int cur_sum = 0;
        int all_sum = 0;

        for (int i = 0; i < cardPoints.size(); i++) {
            all_sum += cardPoints[i];
            cur_sum += cardPoints[i];

            if (i < win_size-1) continue;

            if (cur_sum < min_sum) min_sum = cur_sum;

            cur_sum -= cardPoints[i-win_size+1];
        }

        return all_sum - min_sum;
    }
};

• 正向

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