AlgoViz
HomeSliding Window

Maximum Points You Can Obtain from Cards

Medium

Minimise the middle window instead

Problem

Take exactly k cards from either end of a row to maximize the total points.

In simple words

You pick k cards from either end — slide a window over which few you *leave behind* in the middle.

The idea

Taking k cards from the ends is the same as leaving a contiguous window of n-k cards in the middle. Minimising the sum of that fixed-size window maximises what you take, turning an awkward two-ended choice into an ordinary fixed window.

The trick

  • Answer = total sum - minimum sum of a window of size n-k.
  • Handle k == n: take everything, the window is empty.
  • O(n), one pass.
1
2
3
4
5
6
1
0
1
2
3
4
5
6

Step 1 of 6. Brute force: try taking every split of 3 cards from the two ends. Values: 1, 2, 3, 4, 5, 6, 1.

1/6
Brute force
timeO(k)spaceO(1)

Try every split.

1for (let front = 0; front <= k; front++) {2  const back = k - front;3  best = Math.max(best, sum(first front) + sum(last back));4}

Input

array
[1, 2, 3, 4, 5, 6, 1]

Output

best
—
answer
—

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

Examples

Example 1

Input:
cards = [1, 2, 3, 4, 5, 6, 1], k = 3
Output:
12
Explanation:
Take 1 from the front and 6,5 from the back → 12.

Example 2

Input:
cards = [2, 2, 2], k = 2
Output:
4
Explanation:
Any two cards give 4.

Example 3

Input:
cards = [9, 7, 7, 9, 7, 7, 9], k = 7
Output:
55
Explanation:
Taking every card sums to 55.

Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)

Finished the walkthrough? Add it to your streak.