Sliding Window Fixed-size window
179. Maximum Points You Can Obtain from Cards
A row of cards lies on the table. You are given the row as an array cards, where cards[i] is the number
of points on the card at position i, and an integer k.
You take exactly k cards, one at a time. Each time, you take either the card at the left end of the row or
the card at the right end, and that card leaves the row. Return the largest total number of points that the
k cards you take can add up to.
Points can be negative or zero. You still take exactly k cards, even when a card lowers your total.
Example 1
Input: cards = [2, 8, 1, 1, 5, 5, 3, 9, 3], k = 4
22Explanation: Take 2 and 8 from the left end and 3 and 9 from the right end, for 2 + 8 + 3 + 9 = 22. Taking whichever end card is larger each time picks 3, 9, 3 and 5, which adds up to only 20.
Example 2
Input: cards = [-5, 0, -2, -7, -1], k = 2
-5Explanation: Every choice loses points. Taking −5 and 0 from the left end loses the least, so the answer is −5. Taking one card from each end gives −6, and two from the right gives −8.
Example 3
Input: cards = [2, -3, 4], k = 3
3Explanation: You must take all three cards, so the answer is 2 − 3 + 4 = 3.
Check your understanding
Work out the answer for this input before you write any code.
Constraints
1 ≤ cards.length ≤ 105-109 ≤ cards[i] ≤ 1091 ≤ k ≤ cards.length
Clarifying questions
What you would ask an interviewer before writing any code.