LeetCode 1423. 可獲得的最大點數（逆向思維＋滑動視窗圖解）

1423. 可獲得的最大點數

題目描述

幾張卡牌排成一行，每張卡牌都有一個對應的點數，點數由整數陣列 cardPoints 給出。

每次行動，你可以從行的開頭或者末尾拿一張卡牌，最終你必須正好拿 k 張卡牌。

你的點數就是你拿到手中的所有卡牌的點數之和。

給你一個整數陣列 cardPoints 和整數 k，請你回傳可以獲得的最大點數。

範例 1

輸入：cardPoints = [1,2,3,4,5,6,1], k = 3
輸出：12
解釋：第一次行動，不管拿哪張牌，點數總是 1。但是先拿最右邊的卡牌會最大化可獲得點數。
最優策略是拿右邊的三張牌，最終點數為 1 + 6 + 5 = 12。

範例 2

輸入：cardPoints = [2,2,2], k = 2
輸出：4

範例 3

輸入：cardPoints = [9,7,7,9,7,7,9], k = 7
輸出：55
解釋：必須拿起所有卡牌，點數為所有卡牌點數之和。

範例 4

輸入：cardPoints = [1,1000,1], k = 1
輸出：1
解釋：你無法拿到中間那張卡牌，所以最大點數為 1。

範例 5

輸入：cardPoints = [1,79,80,1,1,1,200,1], k = 3
輸出：202

限制

• 1 <= cardPoints.length <= 10^5
• 1 <= cardPoints[i] <= 10^4
• 1 <= k <= cardPoints.length

本文題解思路與程式碼整理自 LeetCode 題解作者「灵茶山艾府」，題解連結。圖解為自行補充。

前置知識：定長滑動視窗

定長視窗每次右移一格，少一個最左元素、多一個新元素，所以視窗和可以用 s += 新 - 舊 在 O(1) 內更新。前面幾篇（2841、2461）已用過。

方法一：逆向思維

思路

拿走 k 張，剩下 n − k 張（n 是 cardPoints 的長度）。因為

拿走的點數和 + 剩下的點數和 = 所有點數和（常數）

所以要最大化拿走的點數和，就是最小化剩下的點數和。

又因為只能從開頭或末尾拿牌，最後剩下的牌一定是連續的一段。於是問題變成：

計算長為 n − k 的連續子陣列和的最小值。

這就是定長滑動視窗：

1. 設 m = n − k，算第一個長為 m 的子陣列和 s，令 minS = s。
2. 視窗右移一格，s 增加 cardPoints[i] - cardPoints[i - m]，再用 s 更新 minS。
3. 答案 = 全部元素和 − minS。

圖解（可互動）

下面用範例 1 示範方法一：cardPoints = [1,2,3,4,5,6,1]，k = 3，視窗長度 m = 4。視窗是「剩下的牌」，視窗外就是被拿走的牌。

上一步 下一步 重置

cardPoints = [1,2,3,4,5,6,1]，k = 3（剩下的視窗長度 m = n − k = 4）

剩下的牌（視窗） 被拿走的牌 入 = 新進入 出 = 剛離開

視窗總和 s（剩下）0

最小值 minS0

答案 total − minS0

範例 1 的最小值在第一個視窗就出現了，看不到「最佳值被更新」。換一組資料：cardPoints = [3,1,5,2,1,1,6]，k = 3，視窗長度 m = 4，四個視窗和依序是 11、9、9、10。minS 會在第二步從 11 更新成 9，答案 19 − 9 = 10（拿前 2 張加最後 1 張，或前 1 張加最後 2 張，都是 10）。

上一步 下一步 重置

cardPoints = [3,1,5,2,1,1,6]，k = 3（剩下的視窗長度 m = n − k = 4）

剩下的牌（視窗） 被拿走的牌 入 = 新進入 出 = 剛離開

視窗總和 s（剩下）0

最小值 minS0

答案 total − minS0

解法（灵茶山艾府）

class Solution {
    public int maxScore(int[] cardPoints, int k) {
        int n = cardPoints.length;
        int m = n - k;
        int s = 0;
        for (int i = 0; i < m; i++) {
            s += cardPoints[i];
        }

        int total = s;
        int minS = s;
        for (int i = m; i < n; i++) {
            total += cardPoints[i];
            s += cardPoints[i] - cardPoints[i - m];
            minS = Math.min(minS, s);
        }
        return total - minS;
    }
}

當 m = 0（n = k）時也正確：第一個迴圈不執行，s = 0、minS = 0，第二個迴圈只累加 total，最後回傳全部元素和。

複雜度分析

• 時間複雜度：O(n)，其中 n 為 cardPoints 的長度。
• 空間複雜度：O(1)。

方法二：正向思維

思路

拿走的牌一定是「前 j 張 + 後 k − j 張」，j 從 k 到 0。答案是這 k + 1 種組合的最大值：先算前 k 張的和，之後每次把前面的一張換成後面的一張，更新最大值。

圖解（可互動）

方法二看的是「拿走的牌」：先拿前 k 張，之後每一步把頭段最右邊的一張放掉，改拿尾段最左邊的一張，共 k + 1 種組合，ans 取最大值。同樣用範例 1，這次 ans 會一路更新成 6 → 6 → 8 → 12。

上一步 下一步 重置

cardPoints = [1,2,3,4,5,6,1]，k = 3（拿走的牌 = 前 j 張 + 後 k − j 張）

被拿走的牌（頭段＋尾段） 沒被拿的牌 入 = 換進來（尾段） 出 = 換出去（頭段）

前 j 張 ＋ 後 k−j 張0

拿走的點數 s0

最大值 ans0

解法（灵茶山艾府）

class Solution {
    public int maxScore(int[] cardPoints, int k) {
        int s = 0;
        for (int i = 0; i < k; i++) {
            s += cardPoints[i];
        }
        int ans = s;
        for (int i = 1; i <= k; i++) {
            s += cardPoints[cardPoints.length - i] - cardPoints[k - i];
            ans = Math.max(ans, s);
        }
        return ans;
    }
}

複雜度分析

• 時間複雜度：O(k)。
• 空間複雜度：O(1)。

思考題

把題目改成：拿走的卡牌數量無限制，但 cardPoints 中有負數，如何求出可以獲得的最大點數和？（出自題解作者，本文不展開。）