94. Maximum Points You Can Obtain from Cards

There are several cards arranged in a row, and each card has an associated number of points given in the integer array cardPoints. In one step, you can take a card from the beginning or end. You take exactly k cards. Return the maximum score.

Input: Integer array cardPoints and integer k.

Output: Integer — maximum score from k cards.

Examples

Input: [1,2,3,4,5,6,1],3
Output: 12
Explanation: Take cards from right: 1+6+5=12. Or 1+2+3=6 from left. Best: 12.

Input: [2,2,2],2
Output: 4
Explanation: Take 2 from either side. Sum=4.

Input: [9,7,7,9,7,7,9],7
Output: 55
Explanation: Take all 7 cards: sum=55.

Constraints

• 1<=cardPoints.length<=10^5
• 1<=cardPoints[i]<=10^4
• 1<=k<=cardPoints.length

Asked by