1399. Take Coins

There aren coins in a row, each time you want to take a coin from the left or the right side. Take a total of k times to write an algorithm to maximize the value of coins.

• 1 <= k <= n <= 100000。
• The value of the coin is not greater than 10000。

Have you met this question in a real interview?  

Example

Given list = [5,4,3,2,1], k = 2, return 9.

Explanation:
Take two coins from the left.

Given list = [5,4,3,2,1,6], k = 3, return 15.

Explanation:
Take two coins from the left and one from the right.

class Solution { public: /** * @param list: The coins * @param k: The k * @return: The answer */ int takeCoins(vector<int> &list, int k) { // Write your code here int n = list.size(); vector<int> prefixSum(n + 1, 0); for(int i = 0; i < n; i++){ prefixSum[i + 1] = list[i] + prefixSum[i]; } int res = INT_MIN; if(k >= n){ return prefixSum[n]; } else{ for(int i = 0; i <= k; i++){ int sum = prefixSum[i] + prefixSum[n] - prefixSum[n - (k - i)]; res = max(res, sum); } return res; } } };