[Leetcode解題] 1423. Maximum Points You Can Obtain from Cards

18 May 2024

medium array presum sliding-window

題目

1423. Maximum Points You Can Obtain from Cards

有幾張卡片排成一列，每張卡片都有一個對應的點數。這些點數存放在 cardPoints 中。每一步，你可以從這列卡片的開頭或結尾拿走一張卡片，必須恰好拿走 k 張卡片。你的得分是你拿走的卡片點數的總和。

給定 cardPoints 和整數 k，返回你可以獲得的最大得分。

解題思路

這題的關鍵在於如何在拿走 $k$ 張卡片的情況下，最大化總得分。我們可以轉換問題為找出剩下卡片中點數最小的連續子陣列，這樣我們就可以保留總和最大的部分。

具體步驟：

計算陣列中所有卡片的總和。
計算陣列中長度為 $n - k$ 的最小子陣列的總和（$n$ 為卡片數）。
用總和減去這個最小子陣列的總和，得到最大的得分。

Python實現

class Solution:
    def maxScore(self, cardPoints: List[int], k: int) -> int:
        n = len(cardPoints)
        intervalLen = n - k
        total = sum(cardPoints)
        score = sum(cardPoints[:intervalLen])
        minInterval = score

        for i in range(k):
            score = score - cardPoints[i] + cardPoints[i + intervalLen]
            minInterval = min(minInterval, score)

        return total - minInterval

C++實現

class Solution {
public:
    int maxScore(vector<int>& cardPoints, int k) {
        const auto &n = cardPoints.size();
        int intervalLen = n-k;
        int total = accumulate(cardPoints.begin(), cardPoints.end(), 0);
        int score = accumulate(cardPoints.begin(), cardPoints.begin()+intervalLen, 0);
        int minInterval = score;

        for(auto i=0; i<k; i++){
            score = score-cardPoints[i]+cardPoints[i+intervalLen];
            minInterval = min(minInterval, score);
        }
        return total-minInterval;
    }
};