# Maximum Points You Can Obtain from Cards
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/maximum-points-you-can-obtain-from-cards)
Canonical: https://scaleengineer.com/dsa/problems/maximum-points-you-can-obtain-from-cards
**Patterns:** [Sliding Window](https://scaleengineer.com/dsa/patterns/sliding-window), [Prefix Sum](https://scaleengineer.com/dsa/patterns/prefix-sum)
**Data structures:** Array
**Companies:** [Flipkart](https://scaleengineer.com/companies/flipkart), [DE Shaw](https://scaleengineer.com/companies/de-shaw)
---
## Problem
There are several cards **arranged in a row**, and each card has an associated number of points. The points are given in the integer array `cardPoints`.

In one step, you can take one card from the beginning or from the end of the row. You have to take exactly `k` cards.

Your score is the sum of the points of the cards you have taken.

Given the integer array `cardPoints` and the integer `k`, return the _maximum score_ you can obtain.

**Example 1:**

**Input:** cardPoints = [1,2,3,4,5,6,1], k = 3
**Output:** 12
**Explanation:** After the first step, your score will always be 1. However, choosing the rightmost card first will maximize your total score. The optimal strategy is to take the three cards on the right, giving a final score of 1 + 6 + 5 = 12.

**Example 2:**

**Input:** cardPoints = [2,2,2], k = 2
**Output:** 4
**Explanation:** Regardless of which two cards you take, your score will always be 4.

**Example 3:**

**Input:** cardPoints = [9,7,7,9,7,7,9], k = 7
**Output:** 55
**Explanation:** You have to take all the cards. Your score is the sum of points of all cards.

**Constraints:**

* `1 <= cardPoints.length <= 105`
* `1 <= cardPoints[i] <= 104`
* `1 <= k <= cardPoints.length`

# Approaches
## Brute Force Recursion
This approach directly models the problem statement. At each step, we have two choices: take a card from the left end or the right end. We need to make `k` such choices. A recursive function can explore all possible sequences of choices and find the one that yields the maximum score.
**Time:** O(2^k). The recursion tree has a depth of `k`, and each node branches into two, resulting in `2^k` calls at the last level. · **Space:** O(k). The depth of the recursion stack can go up to `k`.
**Pros:** It's a straightforward translation of the problem's decision-making process.; Simple to conceptualize and implement.
**Cons:** Extremely inefficient due to its exponential time complexity.; Will result in a 'Time Limit Exceeded' error for all but the smallest values of `k`.
### Explanation
We define a recursive function, say `findMaxScore(points, left, right, k)`, which calculates the maximum score obtainable from the subarray `points[left...right]` by taking `k` more cards.
The base case for the recursion is when `k` becomes 0, meaning we have taken the required number of cards. In this case, the score to be added is 0, so we return 0.
In the recursive step, we explore the two possible moves:
1. Take the card at the `left` index: The score for this choice is `points[left]` plus the result of the recursive call on the smaller subarray `points[left + 1...right]` with `k-1` cards to take.
2. Take the card at the `right` index: The score for this choice is `points[right]` plus the result of the recursive call on the smaller subarray `points[left...right - 1]` with `k-1` cards to take.
The function returns the maximum of these two scores.
The initial call to this function would be `findMaxScore(cardPoints, 0, cardPoints.length - 1, k)`.
This method explores a binary tree of choices of depth `k`, leading to an exponential number of computations.
```java
class Solution {
    public int maxScore(int[] cardPoints, int k) {
        return findMaxScore(cardPoints, 0, cardPoints.length - 1, k);
    }

    private int findMaxScore(int[] points, int left, int right, int k) {
        // Base case: no more cards to take
        if (k == 0) {
            return 0;
        }

        // Option 1: Take the leftmost card
        int takeLeft = points[left] + findMaxScore(points, left + 1, right, k - 1);

        // Option 2: Take the rightmost card
        int takeRight = points[right] + findMaxScore(points, left, right - 1, k - 1);

        // Return the maximum of the two options
        return Math.max(takeLeft, takeRight);
    }
}
```
### Algorithm
- Define a recursive function `findMaxScore(points, left, right, k)`.
- **Base Case:** If `k == 0`, return 0.
- **Recursive Step:**
  - `scoreLeft = points[left] + findMaxScore(points, left + 1, right, k - 1)`.
  - `scoreRight = points[right] + findMaxScore(points, left, right - 1, k - 1)`.
  - Return `max(scoreLeft, scoreRight)`.
- Initial call: `findMaxScore(cardPoints, 0, n-1, k)`.

## Sliding Window on Middle Subarray
A more clever way to look at the problem is to realize that taking `k` cards from the ends is equivalent to leaving a contiguous subarray of `n-k` cards in the middle. To maximize the sum of the cards taken, we must minimize the sum of the cards left behind. This transforms the problem into finding the minimum sum subarray of a fixed size `n-k`.
**Time:** O(n). We iterate through the array a constant number of times. · **Space:** O(1). We only use a few variables to store sums and indices.
**Pros:** Very efficient with linear time complexity.; Space-efficient as it uses constant extra space.; Solves the problem within the given constraints.
**Cons:** The logic is indirect and requires reframing the problem, which might not be immediately obvious.
### Explanation
First, we calculate the total sum of all points in the `cardPoints` array.
The size of the subarray that will be left is `windowSize = n - k`. Our goal is to find a subarray of this size with the minimum possible sum.
We can use the sliding window technique. We start by calculating the sum of the first window of size `windowSize` (from index 0 to `windowSize - 1`). Let's call this `currentSum`, and initialize `minSum` with this value.
Then, we slide this window one element at a time to the right until it reaches the end of the array. For each slide, we update `currentSum` efficiently by subtracting the element that is leaving the window and adding the new element that is entering.
After each slide, we compare the `currentSum` with `minSum` and update `minSum` if the `currentSum` is smaller.
After iterating through all possible windows, `minSum` will hold the minimum sum of any contiguous subarray of size `n-k`.
The maximum score we can obtain is the `totalSum` minus this `minSum`.
A special case is when `k` is equal to `n`, in which case we must take all cards, and the score is simply the `totalSum`.
```java
class Solution {
    public int maxScore(int[] cardPoints, int k) {
        int n = cardPoints.length;
        int totalSum = 0;
        for (int point : cardPoints) {
            totalSum += point;
        }

        if (k == n) {
            return totalSum;
        }

        int windowSize = n - k;
        int minSubarraySum = 0;

        // Calculate sum of the first window
        for (int i = 0; i < windowSize; i++) {
            minSubarraySum += cardPoints[i];
        }

        int currentSubarraySum = minSubarraySum;
        // Slide the window to find the minimum sum subarray
        for (int i = windowSize; i < n; i++) {
            currentSubarraySum += cardPoints[i] - cardPoints[i - windowSize];
            minSubarraySum = Math.min(minSubarraySum, currentSubarraySum);
        }

        return totalSum - minSubarraySum;
    }
}
```
### Algorithm
- Calculate `totalSum` of all elements in `cardPoints`.
- If `k == n`, return `totalSum`.
- Set `windowSize = n - k`.
- Calculate the sum of the first window `cardPoints[0...windowSize-1]` and store it in `minSum` and `currentSum`.
- Iterate from `i = windowSize` to `n-1`:
  - Update `currentSum` by adding `cardPoints[i]` and subtracting `cardPoints[i - windowSize]`.
  - Update `minSum = min(minSum, currentSum)`.
- Return `totalSum - minSum`.

## Sliding Window on Ends
This approach directly calculates the sums of possible card combinations. We observe that any valid selection of `k` cards is composed of `i` cards from the left and `k-i` cards from the right. We can start with an initial selection (e.g., all `k` cards from the left) and then iteratively modify this selection.
**Time:** O(k). We have an initial loop to sum the first `k` elements, and a second loop that runs `k` times. · **Space:** O(1). Constant extra space is used for variables.
**Pros:** The most time-efficient solution, as its runtime depends on `k`, not `n`.; Very space-efficient.; The logic directly manipulates the selections, which can be intuitive.
**Cons:** The indexing in the loop (`k-1-i` and `n-1-i`) can be slightly tricky to get right initially.
### Explanation
We can think of this as a sliding window of size `k` that wraps around the ends of the array.
First, calculate an initial sum by taking the first `k` cards from the left. This corresponds to taking `k` cards from the left and `0` from the right. Let this be `currentSum`, and initialize `maxSum` with this value.
Now, we iterate `k` times. In each iteration, we simulate taking one less card from the left and one more card from the right.
For example, in the first iteration, we change our selection from `k` left cards to `k-1` left cards and `1` right card. To update the sum, we subtract the rightmost card of our initial left selection (`cardPoints[k-1]`) and add the rightmost card from the whole array (`cardPoints[n-1]`).
We continue this process: in each step `i`, we subtract `cardPoints[k-1-i]` and add `cardPoints[n-1-i]`.
After each update to `currentSum`, we compare it with `maxSum` and update `maxSum` if `currentSum` is larger.
After `k` iterations, we will have considered all `k+1` possible splits (from `k` left/`0` right to `0` left/`k` right), and `maxSum` will hold the maximum possible score.
```java
class Solution {
    public int maxScore(int[] cardPoints, int k) {
        int n = cardPoints.length;
        int currentSum = 0;

        // Calculate the initial sum of the first k cards (k from left, 0 from right)
        for (int i = 0; i < k; i++) {
            currentSum += cardPoints[i];
        }

        int maxSum = currentSum;

        // Slide the window. In each step, we remove one card from the left end
        // of our selection and add one card from the right end of the array.
        for (int i = 0; i < k; i++) {
            // Remove cardPoints[k-1-i] and add cardPoints[n-1-i]
            currentSum = currentSum - cardPoints[k - 1 - i] + cardPoints[n - 1 - i];
            maxSum = Math.max(maxSum, currentSum);
        }

        return maxSum;
    }
}
```
### Algorithm
- Calculate the sum of the first `k` elements. Store this in `currentSum` and `maxSum`.
- Iterate `i` from `0` to `k-1`:
  - This loop simulates changing the pick from `(k-1-i)` left cards and `(i+1)` right cards.
  - Update `currentSum` by subtracting `cardPoints[k-1-i]` (the card no longer taken from the left) and adding `cardPoints[n-1-i]` (the new card taken from the right).
  - Update `maxSum = max(maxSum, currentSum)`.
- Return `maxSum`.

# Solutions
### JavaScript

```javascript
/** * @param {number[]} cardPoints * @param {number} k * @return {number} */ var maxScore =
  function (cardPoints, k) {
    const n = cardPoints.length;
    let s = cardPoints.slice(-k).reduce((a, b) => a + b);
    let ans = s;
    for (let i = 0; i < k; ++i) {
      s += cardPoints[i] - cardPoints[n - k + i];
      ans = Math.max(ans, s);
    }
    return ans;
  };

```

### Java

```java
class Solution { public int maxScore ( int [] cardPoints , int k ) { int s = 0 , n = cardPoints . length ; for ( int i = n - k ; i < n ; ++ i ) { s += cardPoints [ i ]; } int ans = s ; for ( int i = 0 ; i < k ; ++ i ) { s += cardPoints [ i ] - cardPoints [ n - k + i ]; ans = Math . max ( ans , s ); } return ans ; } }
```

### CSharp

```csharp
public class Solution { public int MaxScore ( int [] cardPoints , int k ) { int n = cardPoints . Length ; int s = cardPoints [^ k ..]. Sum (); int ans = s ; for ( int i = 0 ; i < k ; ++ i ) { s += cardPoints [ i ] - cardPoints [ n - k + i ]; ans = Math . Max ( ans , s ); } return ans ; } }
```

### CPP

```cpp
class Solution { public: int maxScore ( vector < int >& cardPoints , int k ) { int n = cardPoints . size (); int s = accumulate ( cardPoints . end () - k , cardPoints . end (), 0 ); int ans = s ; for ( int i = 0 ; i < k ; ++ i ) { s += cardPoints [ i ] - cardPoints [ n - k + i ]; ans = max ( ans , s ); } return ans ; } };
```

### Python

```python
class Solution : def maxScore ( self , cardPoints : List [ int ], k : int ) -> int : ans = s = sum ( cardPoints [ - k :]) for i , x in enumerate ( cardPoints [: k ]): s += x - cardPoints [ - k + i ] ans = max ( ans , s ) return ans
```