381. Predict the Winner
Two players play a game over an integer array nums. Player 1 moves first, and the players alternate. On each turn, the player to move takes either the first or the last element of what remains of the array, removes it, and adds its value to their own score. The game ends when the array is empty.
Both players play perfectly — each always chooses the move that maximizes their own final score assuming the opponent does the same. Return true if Player 1 can end with a score greater than or equal to Player 2's (a tie counts as a win for Player 1), and false otherwise.
Example 1:
Input: nums = [1, 5, 2]
Output: false
Explanation: Player 1 must take 1 or 2, exposing the 5 either way. Player 2 grabs the 5, and Player 1 is left with at most 1 + 2 = 3 against 5. Player 1 cannot reach a tie, so the answer is false.
Example 2:
Input: nums = [1, 5, 233, 7]
Output: true
Explanation: Player 1 takes the 1. Now whichever end Player 2 takes (5 or 7), the 233 sits at an end on Player 1's next turn. Player 1 finishes with at least 234 of the 246 total points.
Constraints:
- 1 ≤ nums.length ≤ 20
- 0 ≤ nums[i] ≤ 10⁷
Hints:
Don't track two scores. From the mover's point of view only one number matters: the margin — (my remaining points) minus (opponent's remaining points). Taking an end earns its value, and then the opponent's best margin on the rest counts against you.
That gives diff(lo, hi) = max(nums[lo] − diff(lo+1, hi), nums[hi] − diff(lo, hi−1)) with diff(i, i) = nums[i]. Player 1 wins exactly when diff(0, n−1) ≥ 0. Plain recursion revisits the same (lo, hi) intervals exponentially often — there are only O(n²) of them, so tabulate by interval length.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: nums = [1, 5, 2]
Expected output: false