思路

贪心策略不行，如果玩家每次都选相对自己当下可选择的最大值，这样的贪心策略有错误，比如这个例子：

输入：nums = [1,5,233,7] 输出：true 解释：玩家 1 一开始选择 1 。然后玩家 2 必须从 5 和 7 中进行选择。无论玩家 2 选择了哪个，玩家 1 都可以选择 233 。 最终，玩家 1（234 分）比玩家 2（12 分）获得更多的分数，所以返回 true，表示玩家 1 可以成为赢家。

java实现

  1. class Solution {
  2.     public boolean PredictTheWinner(int[] nums) {
  3.         return total(nums, 0, nums.length - 1, 1) >= 0;
  4.     }
  6.     public int total(int[] nums, int start, int end, int turn) {
  7.         if (start == end) {
  8.             return nums[start] * turn;
  9.         }
  10.         int scoreStart = nums[start] * turn + total(nums, start + 1, end, -turn);
  11.         int scoreEnd = nums[end] * turn + total(nums, start, end - 1, -turn);
  12.         return Math.max(scoreStart * turn, scoreEnd * turn) * turn;
  13. //        if(turn == 1){
  14. //            return Math.max(scoreStart ,scoreEnd );
  15. //        }else{
  16. //            return Math.min(scoreStart ,scoreEnd );
  17. //        }
  18.     }
  19. }