leet486 预测赢家

玩家 1 和玩家 2 轮流进行自己的回合，玩家 1 先手。开始时，两个玩家的初始分值都是 0 。每一回合，玩家从数组的任意一端取一个数字（即，nums[0] 或 nums[nums.length - 1]），取到的数字将会从数组中移除（数组长度减 1 ）。玩家选中的数字将会加到他的得分上。当数组中没有剩余数字可取时，游戏结束。
如果玩家 1 能成为赢家，返回 true 。如果两个玩家得分相等，同样认为玩家 1 是游戏的赢家，也返回 true
输入：nums = [1,5,2]
输出：false
解释：一开始，玩家 1 可以从 1 和 2 中进行选择。
如果他选择 2（或者 1 ），那么玩家 2 可以从 1（或者 2 ）和 5 中进行选择。如果玩家 2 选择了 5 ，那么玩家 1 则只剩下 1（或者 2 ）可选。
所以，玩家 1 的最终分数为 1 + 2 = 3，而玩家 2 为 5 。
因此，玩家 1 永远不会成为赢家，返回 false 。
方法一，使用递归
思路一：如果我每次取得值与后手比较，差值都大于零，说明我一定会赢
考虑先从左 或者是右边拿的情况。

class Solution {
    public boolean PredictTheWinner(int[] nums) {
int res=max(nums,0,nums.length-1);
if(res>=0){
    return true;
}
return false;
    }
    public int max(int []arr,int l,int r){
    if(l==r){
    return arr[l];
} 
           先手选的   右手选的区间
int lScore=arr[l]-max(arr,l+1,r);
int rScore=arr[r]-max(arr,l,r-1);
return Math.max(lScore,rScore);
}
}

第二种方法
思路
计算出player1可能得到的最大分数，然后用数组总和减去player1的得分就是player2的得分，然后两者比较。
玩家1的得分，等于集合左元素的数值+ 玩家2选择后集合的最小值（因为玩家2也是最聪明的）
代码

class Solution {
    public boolean PredictTheWinner(int[] nums) {
    int sum=0;
for(int i=0;i
sum=sum+nums[i];
}
int play1=max(nums,0,nums.length-1);
int play2=sum-play1;
if(play1>=play2){
    return true;
}

return false;

    }

public int Score(int []arr,int l,int r){
    if(l==r){
        return arr[l];
    }
    int sleft=0;
    int sright=0;
    if(r-l==1){
     sleft=arr[l];
      sright=arr[r];
    }
if(r-l>=2){
  sleft=arr[l]+Math.min(Score(arr,l+2,r),Score(arr,l+1,r-1));
  sright=arr[r]+Math.min(Score(arr,l,r-2),max(arr,l+1,r-1));
}
return Math.max(sleft,sright);
}
}