Coins in a line III

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? 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. Challenge

Follow Up Question:

If n is even. Is there any hacky algorithm that can decide whether first player will win or lose in O(1) memory and O(n) time?

Key Points: $O(n^2) O(2n^2)$

1. Method 1: $f(i,j) = sum[i][j]-min(f(i+1,j),f(i,j-1))$
2. Method 2: $f(i,j) = max(A[i]+min(f(i+1,j-1),f(i+2,j)),A[j]+min(f(i+1,j-1),f(i,j-2)))$
3. Compare to Method 1, Method 2 takes no extra space or time to store sums, but a little bit more complex on computation order.

public boolean firstWillWin(int[] values) {
        int len = values.length;
        if(len==0){return false;}
        if(len==1){return true;}

        //f(i,j) = max(A[i]+sum[i+1,j]-f(i+1,j),A[j]+sum[i,j-1]-f(i,j-1))
        //f(i,j) = sum[i,j]-Math.min(f(i+1,j),f(i,j-1))
        int[][] sum = new int[len][len];
        int[][] res = new int[len][len];


        for(int i=0; i<len; i++){
            int total = 0;
            for(int j=i; j<len; j++){
                total+=values[j];
                sum[i][j] = total;
            }
        }


        for(int i = len-2; i>=0; i--){
            for(int j =1 ; j<len; j++){
                if(j>=i){
                res[i][j] = sum[i][j] - Math.min(res[i+1][j],res[i][j-1]);

                }
            }
        }

        return res[0][len-1]>sum[0][len-1]/2;
    }