minimax

图片说明
class Solution {
    public boolean PredictTheWinner(int[] nums) {
        if(nums==null || nums.length==0) return true;
        
        return getGap(0,nums.length-1,nums)>=0;
    }
    
    public int getGap(int l,int r,int[] nums){
        if(l==r) return nums[l];
        
        return Math.max(nums[l] - getGap(l+1,r,nums),
                        nums[r] - getGap(l,r-1,nums));
    }
   
}