Coins in a Line III

Here are n coins in a line. Two players take turns to take ONE coin from one of the ends of the line until there are no more coins left. The player with the larger amount of money wins. Could you please decide the first player will win or lose?

Example:

Given array A = [3,2,2], return true.

Given array A = [1,2,4], return true.

Given array A = [1,20,4], return false.

Solution:

In Coins in a Line II, players take coins only from one side, so we could only use one array to store the total values of remaining coins at any time. However, players are allowed to take coins from both sides of the line in this question. Therefore, we have to track the total values of an interval and we also need an matrix to store each solution for any interval.

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;
        }
        int n = values.length;
        int[] sum = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            sum[i] = sum[i - 1] + values[i - 1];
        }
        int[][] f = new int[n][n];
        for (int i = 0; i < n; i++) {
            f[i][i] = values[i];
        }
        for (int len = 2; len <= n; len++) {
            for (int i = 0; i < n; i++) {
                int j = i + len - 1;
                if (j >= n) {
                    continue;
                }
                int s = sum[j + 1] - sum[i];
                f[i][j] = Math.max(s - f[i + 1][j], s - f[i][j - 1]);
            }
        }
        return f[0][n - 1] > sum[n] / 2;
    }
}