题目

几张卡牌 排成一行，每张卡牌都有一个对应的点数。点数由整数数组 cardPoints 给出。

每次行动，你可以从行的开头或者末尾拿一张卡牌，最终你必须正好拿 k 张卡牌。

你的点数就是你拿到手中的所有卡牌的点数之和。

给你一个整数数组 cardPoints 和整数 k，请你返回可以获得的最大点数。

题目来源：https://leetcode.cn/problems/maximum-points-you-can-obtain-from-cards/description/

示例

示例 1

示例 2

示例 3

题解

方法一：逆向思维

分析

拿走 k 张，剩下 n−k 张。这里 n 是 cardPoints 的长度。
由于拿走的点数和 + 剩下的点数和 = 所有点数和 = 常数，所以为了最大化拿走的点数和，应当最小化剩下的点数和。

因为只能在开头和末尾拿走，所以最后剩下的n-k张牌必是连续的。
至此题目就转换为 计算长为 n−k 的连续子数组和的最小值。
利用定滑窗口即可解决。

代码

class Solution {
public:
    int maxScore(vector<int>& cardPoints, int k) {
        int len = cardPoints.size();
        int m = len - k;
        long long sum = 0, min_sum = 0,total_sum = 0;
        int i = 0;
        for (; i < m; i++) {
            sum += cardPoints[i];
        }
        total_sum = min_sum = sum;
        for (; i < len; i++) {
            total_sum += cardPoints[i];
            sum += cardPoints[i] - cardPoints[i-m];
            min_sum = min(sum, min_sum);
        }
        return total_sum - min_sum;
    }
};

复杂度分析

• 时间复杂度：O(n)，其中 n 为 cardPoints 的长度。
• 空间复杂度：O(1)。Python 忽略切片开销。

方法二：正向思维

分析

由于只能在开头和末尾拿走，假设在开头拿走了 m 张，那么剩下的 k-m 张就只能从末尾拿。
此时所有拿走的 k 张牌点数和就为 cardPoints[0] + cardPoints[1] + ··· + cardPoints[m-1] + cardPoints[n-k+m] + cardPoints[n-k+m+1] + ··· + cardPoints[n-1]

那么所有拿走的点数和最大值为以下结果的最大值：

• 前 k 个数的和。
• 前 k−1 个数以及后 1 个数的和。
• 前 k−2 个数以及后 2 个数的和。
• ……
• 前 2 个数以及后 k−2 个数的和。
• 前 1 个数以及后 k−1 个数的和。
• 后 k 个数的和。

代码

class Solution {
public:
    int maxScore(vector<int>& cardPoints, int k) {
        int len = cardPoints.size();
        long long sum = 0, max_sum = 0;
        int i = 0;
        for (; i < k; i++) {
            sum += cardPoints[i];
        }
        max_sum = sum;
        for (; i > 0; i--) {
            sum += cardPoints[len-(k-(i-1))] - cardPoints[i-1];
            max_sum = max(sum, max_sum);
        }
        return max_sum;
    }
};

复杂度分析

• 时间复杂度：O(k)。
• 空间复杂度：O(1)。Python 忽略切片开销。