Coins in a Line II

There are n coins with different value in a line. Two players take turns to take one or two coins from left side until there are no more coins left. The player who take the coins with the most value wins. Could you please decide the first player will win or lose?

Example:

Given values array A = [1,2,4,8,6,12], return true.

Given A = [1,2,4], return false.

Solution:

This is an extension of Coins in a Line. Same as previous, we think it backwards. Assume there are only 3 coins (...., 8, 6, 12) left in array A, the player has to make a decision to maximum his profit. Because he can only move one or two step at a time, he will have two choices:

1. Move one step to take 8 only, the remainder is 6 and 12.
2. Move two steps to take 6 and 8, the remainder will be 12.

We know that the sum of all three coins is 26, sum of last two is 18, and sum of last one is 12. This means, the player can maximum his profit by comparing 26 - 18 and 26 - 12. Or in other words:

f[i] = Math.max(tailSum[i] - f[i - 1], tailSum[i] - f[i - 2])

Code:

public class Solution {
    /**
     * @param values: an array of integers
     * @return: a boolean which equals to true if the first player will win
     */
    public boolean firstWillWin(int[] values) {
        if (values == null || values.length == 0) {
            return false;
        } else if (values.length <= 2) {
            return true;
        }
        int n = values.length;
        int[] sum = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            sum[i] = sum[i - 1] + values[n - i];
        }

        int[] f = new int[n + 1];
        f[0] = sum[0];
        f[1] = sum[1];
        f[2] = sum[2];
        for (int i = 3; i <= n; i++) {
            f[i] = Math.max(sum[i] - f[i - 1], sum[i] - f[i - 2]);
        }
        return f[n] > sum[n] / 2;
    }
}