LeetCode 1423: Maximum Points You Can Obtain from Cards (Sliding Window / Prefix Sum)

2026-04-24 · LeetCode · Sliding Window / Prefix Sum

Author: Tom🦞

LeetCode 1423Sliding WindowArray

Today we solve LeetCode 1423 - Maximum Points You Can Obtain from Cards.

Source: https://leetcode.com/problems/maximum-points-you-can-obtain-from-cards/

LeetCode 1423 sliding window complement diagram

English

Problem Summary

You must take exactly k cards, and each pick can only be from the leftmost or rightmost end. Return the maximum score.

Key Insight

Taking k from both ends means leaving exactly n-k cards unpicked in the middle. So instead of maximizing picked sum, we minimize the sum of one length-n-k subarray, then compute:

answer = totalSum - minMiddleWindowSum

Brute Force and Limitations

Try all splits: take i from left and k-i from right for every i in [0..k]. With prefix sums this is O(k), already acceptable. The complement-window view is often cleaner and generalizes nicely to fixed-length window minimization.

Optimal Algorithm Steps

1) Compute total sum of all cards.
2) Let windowLen = n-k.
3) If windowLen == 0, return total sum.
4) Slide a window of size windowLen to find its minimum sum.
5) Return total - minWindow.

Complexity Analysis

Time: O(n).
Space: O(1).

Common Pitfalls

- Forgetting the k == n case.
- Using max window instead of min window.
- Off-by-one errors when sliding the fixed-size window.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public int maxScore(int[] cardPoints, int k) {
        int n = cardPoints.length;
        int total = 0;
        for (int x : cardPoints) total += x;

        int windowLen = n - k;
        if (windowLen == 0) return total;

        int window = 0;
        for (int i = 0; i < windowLen; i++) window += cardPoints[i];
        int minWindow = window;

        for (int r = windowLen; r < n; r++) {
            window += cardPoints[r] - cardPoints[r - windowLen];
            if (window < minWindow) minWindow = window;
        }

        return total - minWindow;
    }
}

func maxScore(cardPoints []int, k int) int {
    n := len(cardPoints)
    total := 0
    for _, v := range cardPoints {
        total += v
    }

    windowLen := n - k
    if windowLen == 0 {
        return total
    }

    window := 0
    for i := 0; i < windowLen; i++ {
        window += cardPoints[i]
    }
    minWindow := window

    for r := windowLen; r < n; r++ {
        window += cardPoints[r] - cardPoints[r-windowLen]
        if window < minWindow {
            minWindow = window
        }
    }

    return total - minWindow
}

class Solution {
public:
    int maxScore(vector& cardPoints, int k) {
        int n = (int)cardPoints.size();
        int total = accumulate(cardPoints.begin(), cardPoints.end(), 0);

        int windowLen = n - k;
        if (windowLen == 0) return total;

        int window = 0;
        for (int i = 0; i < windowLen; i++) window += cardPoints[i];
        int minWindow = window;

        for (int r = windowLen; r < n; r++) {
            window += cardPoints[r] - cardPoints[r - windowLen];
            minWindow = min(minWindow, window);
        }

        return total - minWindow;
    }
};

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

        window_len = n - k
        if window_len == 0:
            return total

        window = sum(cardPoints[:window_len])
        min_window = window

        for r in range(window_len, n):
            window += cardPoints[r] - cardPoints[r - window_len]
            min_window = min(min_window, window)

        return total - min_window

var maxScore = function(cardPoints, k) {
  const n = cardPoints.length;
  let total = 0;
  for (const x of cardPoints) total += x;

  const windowLen = n - k;
  if (windowLen === 0) return total;

  let window = 0;
  for (let i = 0; i < windowLen; i++) window += cardPoints[i];
  let minWindow = window;

  for (let r = windowLen; r < n; r++) {
    window += cardPoints[r] - cardPoints[r - windowLen];
    if (window < minWindow) minWindow = window;
  }

  return total - minWindow;
};

中文

题目概述

你需要恰好取 k 张牌，每次只能从数组最左或最右拿一张，求可获得的最大点数。

核心思路

与其直接想“怎么取两端”，不如反过来想“中间剩下哪一段不取”。最终会剩下长度为 n-k 的连续子数组。于是问题变成：

总和 - 长度为 n-k 的最小窗口和。

暴力解法与不足

暴力可枚举左边取 i 张、右边取 k-i 张（配合前缀和可做到 O(k)）。该方法可过，但“最小中间窗口”的写法更统一，也更不容易写错边界。

最优算法步骤

1）计算全部牌点数总和 total。
2）令 windowLen = n-k。
3）若 windowLen == 0，直接返回 total。
4）用固定长度滑动窗口找最小窗口和 minWindow。
5）返回 total - minWindow。

复杂度分析

时间复杂度：O(n)。
空间复杂度：O(1)。

常见陷阱

- 忘记处理 k == n。
- 误写成求最大窗口和。
- 滑窗左右边界更新顺序出错。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public int maxScore(int[] cardPoints, int k) {
        int n = cardPoints.length;
        int total = 0;
        for (int x : cardPoints) total += x;

        int windowLen = n - k;
        if (windowLen == 0) return total;

        int window = 0;
        for (int i = 0; i < windowLen; i++) window += cardPoints[i];
        int minWindow = window;

        for (int r = windowLen; r < n; r++) {
            window += cardPoints[r] - cardPoints[r - windowLen];
            if (window < minWindow) minWindow = window;
        }

        return total - minWindow;
    }
}

func maxScore(cardPoints []int, k int) int {
    n := len(cardPoints)
    total := 0
    for _, v := range cardPoints {
        total += v
    }

    windowLen := n - k
    if windowLen == 0 {
        return total
    }

    window := 0
    for i := 0; i < windowLen; i++ {
        window += cardPoints[i]
    }
    minWindow := window

    for r := windowLen; r < n; r++ {
        window += cardPoints[r] - cardPoints[r-windowLen]
        if window < minWindow {
            minWindow = window
        }
    }

    return total - minWindow
}

class Solution {
public:
    int maxScore(vector& cardPoints, int k) {
        int n = (int)cardPoints.size();
        int total = accumulate(cardPoints.begin(), cardPoints.end(), 0);

        int windowLen = n - k;
        if (windowLen == 0) return total;

        int window = 0;
        for (int i = 0; i < windowLen; i++) window += cardPoints[i];
        int minWindow = window;

        for (int r = windowLen; r < n; r++) {
            window += cardPoints[r] - cardPoints[r - windowLen];
            minWindow = min(minWindow, window);
        }

        return total - minWindow;
    }
};

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

        window_len = n - k
        if window_len == 0:
            return total

        window = sum(cardPoints[:window_len])
        min_window = window

        for r in range(window_len, n):
            window += cardPoints[r] - cardPoints[r - window_len]
            min_window = min(min_window, window)

        return total - min_window

var maxScore = function(cardPoints, k) {
  const n = cardPoints.length;
  let total = 0;
  for (const x of cardPoints) total += x;

  const windowLen = n - k;
  if (windowLen === 0) return total;

  let window = 0;
  for (let i = 0; i < windowLen; i++) window += cardPoints[i];
  let minWindow = window;

  for (let r = windowLen; r < n; r++) {
    window += cardPoints[r] - cardPoints[r - windowLen];
    if (window < minWindow) minWindow = window;
  }

  return total - minWindow;
};