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):

 

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;
    }
}