Domain 2MediumMEDIUM

Maximum Points You Can Obtain from Cards

Calculate the total sum of all cards, then find the minimum subarray sum of length (N-k). The maximum score is the total minus this minimum remaining sum.

Domain: medium•Updated: 2026-09-16
#sliding window#array#$O(N)$#$O(1)

Problem Breakdown

We are given an array cardPoints and an integer k. We must select exactly k cards from either end of the row to maximize their point sum. Since we take ii cards from the left, we implicitly leave (N−k)(N-k) cards in a contiguous middle subarray (where 0≤i≤k0 \le i \le k). Maximizing the taken points is equivalent to minimizing the remaining points in that specific window size (window_size=N−kwindow\_size = N - k).

Inputs:

  • cardPoints: List[int] representing card values. Length NN.
  • k: int, number of cards to take.

Outputs:

  • Integer: Maximum possible score obtained by taking exactly k cards from ends.

Intuition

A brute-force approach would iterate through all valid combinations (ii left, k−ik-i right), calculating the sum for each split point. This results in roughly O(N⋅k)O(N \cdot k) or O(k2)O(k^2) time complexity if sums are recalculated naively.

Key Insight: Instead of maximizing the selected cards directly, consider what is left behind. The set of taken cards plus the remaining middle subarray equals the entire array sum. To maximize the score (taken cards), we must equivalently minimize the sum of the (N−k)(N-k) cards left in the contiguous middle section. This transforms the problem into finding a minimum sum subarray of fixed length window_size=N−kwindow\_size = N - k.

Approach

  1. Calculate Total: Compute total_sum for all elements in cardPoints.
  2. Handle Edge Case: If k == n, we take everything, so return total_sum. This avoids window logic issues when the remaining count is zero.
  3. Determine Window Size: The number of cards not taken (remaining) is window_size = n - k.
  4. Sliding Window Initialization: Calculate the sum of the first contiguous subarray of length window_size starting at index 0. Store this in min_middle_sum.
  5. Slide and Update: Iterate through the array, updating the current window sum by adding the new element entering from the right and subtracting the old element leaving from the left. Track the minimum sum encountered (min_middle_sum).
  6. Result Calculation: Return total_sum - min_middle_sum.

Complexity Analysis

  • Time Complexity: O(N)O(N), where NN is the length of cardPoints. We iterate through the array to compute the total sum and then slide a window across it once. Each element is accessed a constant number of times.
  • Space Complexity: O(1)O(1). Only primitive variables (total_sum, current_window_sum, etc.) are used, independent of input size.

Solution

def maxScore(cardPoints: list[int], k: int) -> int:
    n = len(cardPoints)
    
    # Calculate the sum of all cards (baseline total points available)
    total_sum = sum(cardPoints)
    
    # If we take all cards, return the total sum immediately. 
    if k == n:
        return total_sum
    
    # The number of elements remaining (not taken) forms a contiguous subarray
    window_size = n - k
    
    current_window_sum = 0
    
    # Initialize the first sliding window sum for the 'remaining' cards
    for i in range(window_size):
        current_window_sum += cardPoints[i]
    
    min_middle_sum = current_window_sum
    
    # Slide the window across the array to find the minimum subarray sum of length (n - k)
    # We start sliding from index 'window_size' up to n-1
    for i in range(window_size, n):
        # Add element entering the window at index i
        current_window_sum += cardPoints[i]
        # Remove element leaving the window at index i - window_size
        current_window_sum -= cardPoints[i - window_size]
        
        # Update minimum sum found so far for the remaining cards
        if current_window_sum < min_middle_sum:
            min_middle_sum = current_window_sum
            
    return total_sum - min_middle_sum

Edge Cases Handled

  • k==nk == n: The code explicitly checks this. If we must take all cards, window_size would be 0. By handling k==nk==n, we avoid iterating over an empty range and correctly return the sum of all elements without needing to subtract a zero-sum window (though mathematically valid).
  • k==1k == 1: The logic holds; it finds the minimum single element in the middle, effectively maximizing one end.
  • Small Array: Works for N=KN=K.
  • Large Values: Python handles large integers automatically preventing overflow issues common in fixed-width integer languages like C++ or Java (though constraints fit within 32-bit signed int anyway).