There are_n_coins in a line. Two players take turns to take a 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?

Have you met this question in a real interview?

Yes

Example

Given array A =[3,2,2], returntrue.

Given array A =[1,2,4], returntrue.

Given array A =[1,20,4], returnfalse.

public class Solution {
    /*
     * @param : a vector of integers
     * @return: a boolean which equals to true if the first player will win
     */
    //set X(Alice) and Y(Bob) are the total value each player get
    //so when X got to move first, it wants the difference to be max Sx = X - Y
    //   when Y got to move first, it wants the difference to be max Sy = Y - X
    //   therefore after the next move X make, Sx = -Sy + m
    //set f[i][j] represents a[i, j] one side first move the max difference
    //f[i][j] = max{a[i] - f[i + 1][j], a[j] - f[i][j - 1]}
    public boolean firstWillWin(int[] values) {
        // write your code here
        if (values == null && values.length == 0) {
            return false;
        }

        int n = values.length;
        int[][] f = new int[n][n];
        //init
        //if there is only one number the first hand got the item value
        int i, j, len;
        for (i = 0; i < n; i++) {
            f[i][i] = values[i];
        }


        for (len = 2; len <= n; len++) {
            for (i = 0; i <= n - len; i++) {
                j = i + len - 1;
                f[i][j] = Math.max(values[i] - f[i + 1][j], values[j] - f[i][j - 1]);
            }
        }

        return f[0][n - 1] >= 0;
    }
};