486. 预测赢家🔖数组

• https://leetcode-cn.com/problems/predict-the-winner/

思路

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

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

java 实现

class Solution {
    public boolean PredictTheWinner(int[] nums) {
        return total(nums, 0, nums.length - 1, 1) >= 0;
    }

    public int total(int[] nums, int start, int end, int turn) {
        if (start == end) {
            return nums[start] * turn;
        }
        int scoreStart = nums[start] * turn + total(nums, start + 1, end, -turn);
        int scoreEnd = nums[end] * turn + total(nums, start, end - 1, -turn);
        return Math.max(scoreStart * turn, scoreEnd * turn) * turn;
//        if(turn == 1){
//            return Math.max(scoreStart ,scoreEnd );
//        }else{
//            return Math.min(scoreStart ,scoreEnd );
//        }
    }
}