Maximum Ends Sum

Given an integer array nums and an integer k, take exactly k elements from the array. Each take removes either the current first element or the current last element of the array.

Return the maximum possible sum of the taken elements.

Equivalently: choose some i elements from the front of nums and k - i elements from the back (for any i between 0 and k), maximizing their total.

Examples

Example 1

Input: nums = [1,2,3,4,5,6,1], k = 3
Output: 12
Explanation: Taking the last three elements gives 1 + 6 + 5 = 12, the maximum possible. Any selection that includes elements from the front locks in smaller values.

Example 2

Input: nums = [2,2,2], k = 2
Output: 4
Explanation: Every choice of two elements sums to 4.

Example 3

Input: nums = [9,7,7,9,7,7,9], k = 7
Output: 55
Explanation: k equals the length of nums, so every element is taken; the sum is 55.