MediumRating 1574
1423. Maximum Points You Can Obtain from Cards
arraysliding-windowprefix-sum
解題說明
Maximum Points You Can Obtain from Cards
題目描述：
有一排卡牌 cardPoints，每次只能從最左邊或最右邊取一張牌，總共取 k 張。求能獲得的最大點數和。
解題思路：
取 k 張牌等於「從左邊取 i 張 + 從右邊取 k-i 張」（i 從 0 到 k）。我們可以反向思考：取 k 張牌後，剩下的是中間連續的 n-k 張牌。最大化取走的分數，等價於最小化中間連續子陣列（長度 n-k）的分數和。
使用滑動窗口找長度為 n-k 的最小子陣列和，答案就是 totalSum - minWindowSum。
或者直接枚舉：先計算取左邊 k 張的總和，然後逐步把左邊的牌放回、從右邊取牌，更新最大值。
C++ 解法
複雜度分析
時間複雜度：O(k) — 兩次遍歷各 k 步。
空間複雜度：O(1) — 只使用常數額外空間。
虛擬碼
1. Compute sum of first k cards (all from left) 2. Set ans = sum 3. For i from k-1 down to 0: a. Remove cardPoints[i] from sum (give back left card) b. Add cardPoints[n - k + i] to sum (take right card) c. ans = max(ans, sum) 4. Return ans
其他解法
滑動窗口求最小子陣列和：計算 totalSum，然後用大小 n-k 的滑動窗口找最小子陣列和 minSum。答案 = totalSum - minSum。時間 O(n)，空間 O(1)。邏輯正確但遍歷整個陣列，稍慢於直接枚舉法的 O(k)。
前綴和 + 後綴和：預計算前綴和與後綴和陣列，枚舉左取 i 張、右取 k-i 張的所有組合。時間 O(n)，空間 O(n)。直觀但空間較大。
延伸思考
- 若可以從左邊取最多 a 張、右邊取最多 b 張（a + b >= k），如何修改？
- 若不限制取牌數量，但有一個「最低分數」門檻，要求取的牌總分不低於門檻，求最少取幾張？
- 若牌不是一排而是環形排列，問題會如何變化？