[snap]A and B play game

原题

package snapchat;

/**
 * Created by kangyue on 1/5/17.
 */
public class PlayGame {
    public int play(int[] arr){
        if(arr.length == 0)return 0;
        if(arr.length == 1)return arr[0];

        int len = arr.length;
        int[][] dp = new int[len][len];

        for(int i = 0; i < len; i++){
            dp[i][i] = arr[i];
        }

        for(int i = 0; i < len - 1; i++){
            dp[i][i + 1] = Math.max(arr[i],arr[i + 1]);
        }

        for(int step = 2; step < len; step++){
            for(int i = 0; i < len - step; i++){
                int removeFirst = arr[i + 1] > arr[i + step] ? dp[i + 2][i + step] : dp[i + 1][i + step - 1];
                int removeLast = arr[i] > arr[i + step - 1] ? dp[i + 1][i + step - 1] : dp[i][i + step - 2];
                dp[i][i + step] = Math.max(arr[i] + removeFirst,arr[i + step] + removeLast);
            }
        }


        return dp[0][len - 1];
    }

    public static void main(String[] args){
        PlayGame pg = new PlayGame();
        System.out.println(pg.play(new int[]{3,7,2,1}));
    }
}