163. Cards From the Ends
Cards lie in a single row on a table, and the number of points printed on the card at position i is points[i]. In one move you may take either the leftmost remaining card or the rightmost remaining card, and its points are added to your score.
You must make exactly k moves. You are free to decide the side for each move, so you may take only from the left, only from the right, or any mix. Return the maximum score you can collect after exactly k cards have been taken.
Example 1
- Input:
- points = [3,1,1,9,2,4], k = 3
- Output:
- 15
- Explanation:
Taking the three rightmost cards 4, 2 and 9 scores 15. Other splits are worse, for example the cards 3, 1 and 4 (two from the left, one from the right) score only 8.
Example 2
- Input:
- points = [5,5,5], k = 3
- Output:
- 15
- Explanation:
You must take all three cards, so the score is 15.
Example 3
- Input:
- points = [1,100,1], k = 1
- Output:
- 1
- Explanation:
Only an end card can be taken, so the best single move scores 1, even though the middle card is worth 100.
Constraints
1 ≤ points.length ≤ 105
1 ≤ points[i] ≤ 104
1 ≤ k ≤ points.length
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 1,200 msC++ 300 msJava 600 msJavaScript 600 msTypeScript 600 ms
Expected complexity
- Time
- O(k)
- Space
- O(1)