Lintcode1399. Take Coins

1399. Take Coins

中文English

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.

Example

Example 1:

Input: list = [5,4,3,2,1], k = 2
Output :9
Explanation:Take two coins from the left.

Example 2:

Input: list = [5,4,3,2,1,6], k = 3, 
Output:15
Explanation:Take two coins from the left and one from the right.

Notice

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

Wrong solution:

Greedy. Two pointers from the start and end of the array, respectively. Each time get the larger value until k times. The reason it doesn't work is one example [4, 1, 1, 1, 6, 1] and k = 2. For the greedy. We take 4 and 1, so the value is 5. However, the max value we can get is to get 6 and 1, which is 7 instead. 

Correct Solution:

The correct solution is we can take k from left, then 0 from right, e.g.

from left      from  right

k                     0

k - 1                1

k - 2                2

...                    ...

0                     k

So the solution is we first get sum of the first k elements from the left. And then each time we get one from right, we substract from the left side. 

Code (Java):

 

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40

public class Solution {     /**      * @param list: The coins      * @param k: The k      * @return: The answer      */     public int takeCoins(int[] list, int k) {         // Write your code here         if (list == null || list.length == 0) {             return 0;         }                   int sum = 0;         int maxSum = 0;                   int left = 0;         int right = list.length - 1;                   for (left = 0; left < k; left++) {             sum += list[left];         }                   maxSum = sum;                   // left pointer back off by one         left--;                   while (left >= 0) {             sum -= list[left];             left--;                           sum += list[right];             right--;                           maxSum = Math.max(maxSum, sum);         }                   return maxSum;     } }