Maximum Points You Can Obtain from Cards
Understanding the Problem
We have a row of cards, and we need to pick exactly k cards, but with a restriction: each pick must come from either the left end or the right end of the remaining row. We want to maximize the total points.
A greedy rule of always picking the larger end does not work. Consider [5, 2, 10, 1, 3] with k = 3. Greedy picks 5 (left), then 3 (right), then 2 (left), totaling 10. The optimal play is to take all three from the left: 5 + 2 + 10 = 17. Choosing the larger end at each step ignores the high-value card sitting just behind a smaller one.
There is a more useful way to frame the selection. Whatever k cards we pick from the ends, the remaining n - k cards form a contiguous subarray in the middle. Instead of deciding which cards to take, we can decide which contiguous subarray of length n - k to leave behind. Minimizing the sum of the leftover window maximizes our score.
Key Constraints:
1 <= cardPoints.length <= 10^5→ With n up to 100,000, we need O(n) or O(n log n). Anything O(n^2) risks timing out.1 <= cardPoints[i] <= 10^4→ All values are positive, so the total never overflows a 32-bit integer (at most 10^5 × 10^4 = 10^9, within the ~2.1 × 10^9 limit of a signed int).1 <= k <= cardPoints.length→ k can equal n, meaning we take every card and leave an empty window. The window-size-zero case needs explicit handling.
Approach 1: Brute Force (Recursion)
Intuition
At each step, we choose to take from the left or the right, try both options recursively, and pick whichever gives a higher total.
This models the problem description directly. At each of the k steps we branch into two choices (take left, take right), building a binary decision tree, and return the maximum sum across all paths.
Algorithm
- Define a recursive function that takes the current left index, current right index, and the number of cards remaining to pick.
- Base case: if no cards remain to pick, return 0.
- Recursive case: return the maximum of:
- Taking the left card:
cardPoints[left] + recurse(left + 1, right, remaining - 1) - Taking the right card:
cardPoints[right] + recurse(left, right - 1, remaining - 1) - Call the function with
left = 0,right = n - 1, andremaining = k.
Visualization and Code
Loading animation...
- Time Complexity: O(2^k). At each step we branch into two choices, and we make k choices total, creating a binary tree of depth k.
- Space Complexity: O(k). The recursion depth is k, since we make one recursive call per card we take.
This approach explores every possible combination but is too slow for large inputs, with up to 2^k recursive paths. The next approach flips the perspective: instead of choosing which k cards to pick, it identifies which n - k cards to leave behind.
Approach 2: Sliding Window (Minimum Window Sum)
Intuition
Whatever k cards we pick from the ends, the cards we don't pick form a contiguous subarray of length n - k in the middle. Taking 2 cards from the left and 1 from the right (with k = 3) leaves one unbroken block, and the same holds for every left-right split.
The problem becomes: find the contiguous subarray of length n - k with the minimum sum, then subtract it from the total sum of all cards. That is a fixed-size sliding window over the array.
Picking i cards from the left and k - i from the right leaves exactly the block from index i to n - (k - i) - 1, a contiguous run of n - k cards. As i ranges from 0 to k, this leftover block slides across every position a window of length n - k can occupy, and each such window corresponds to exactly one valid pick. So the set of valid picks and the set of length-n - k windows are in one-to-one correspondence. Since picked sum = total sum - leftover sum, maximizing the picked sum is the same as minimizing the leftover window sum.
Algorithm
- Compute the total sum of all cards.
- Set the window size to
n - k. - Compute the sum of the first window (indices 0 to
windowSize - 1). - Set
minWindowSumto this initial window sum. - Slide the window one position at a time: add the new element entering from the right, subtract the element leaving from the left.
- Update
minWindowSumwhenever the current window sum is smaller. - Return
totalSum - minWindowSum.
Visualization and Code
Loading animation...
- Time Complexity: O(n). We make one pass to compute the total sum, then one pass to slide the window. Each element is visited at most twice.
- Space Complexity: O(1). We only use a few integer variables regardless of input size.
The sliding window approach is optimal. The next approach reaches the same answer from the other direction: instead of minimizing the middle window, it iterates over every split of the k taken cards between the left and right ends.
Approach 3: Direct Left-Right Split
Intuition
If we take k cards total, some come from the left and some come from the right. Specifically, we take i cards from the left and k - i cards from the right, where i ranges from 0 to k. We start by assuming we take all k cards from the left, then "swap" one left card for one right card at a time, tracking the maximum sum.
Algorithm
- Compute the sum of the first
kcards (all from the left). This is our starting point. - Set
maxScoreto this initial sum. - For
ifrom 1 to k: - Remove the card at position
k - ifrom the left (subtract it). - Add the card at position
n - ifrom the right (add it). - Update
maxScoreif this new sum is larger. - Return
maxScore.
Visualization and Code
Loading animation...
- Time Complexity: O(k). We compute the initial sum of k elements, then iterate k more times. Since k <= n, this is O(n) in the worst case but can be much faster when k is small.
- Space Complexity: O(1). Only a few integer variables are used.