1423 可获得的最大点数

一、题目

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

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

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

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

二、题解

思路：逆向思考与滑动窗口

既然这 $k$ 张牌分布在左右两端，我们可以枚举所有可能的组合情况：

1. 左边拿 $k$ 张，右边拿 0 张。
2. 左边拿 $k-1$ 张，右边拿 1 张。
3. ...
4. 左边拿 0 张，右边拿 $k$ 张。 我们可以先计算出“全部从左边拿”的总点数。然后，我们像滑动窗口一样，每次吐出左边最右侧的一张牌，吞入右边最左侧的一张牌，并实时更新最大点数。

class Solution {
    public int maxScore(int[] cardPoints, int k) {
        int n = cardPoints.length;
        int currentSum = 0;

        // 1. 初始化窗口：假设这 k 张牌全部从左边拿
        for (int i = 0; i < k; i++) {
            currentSum += cardPoints[i];
        }

        int maxSum = currentSum;

        // 2. 开始滑动窗口：逐步用右边的牌替换左边的牌
        for (int i = 1; i <= k; i++) {
            // 放回左边第 k - i 张牌 (cardPoints[k - i])
            // 拿走右边倒数第 i 张牌 (cardPoints[n - i])
            currentSum = currentSum - cardPoints[k - i] + cardPoints[n - i];
            maxSum = Math.max(maxSum, currentSum);
        }

        return maxSum;
    }
}

时间复杂度：$O(k)$

空间复杂度：$O(1)$