End-Picking Number Game: Can the First Player Win Under Optimal Play?

Two players play a game on a row of non-negative integers nums. They alternate turns, and Player 1 moves first. On each turn, the current player removes either the leftmost or the rightmost remaining number and adds it to their own score. The game ends when no numbers remain.

Both players play optimally. Return whether Player 1 can finish with a score at least as large as Player 2's.

Function Signature

def first_player_can_win(nums: list[int]) -> bool:

Rules

• Both scores start at 0.
• "Optimally" means each player always chooses the move that maximizes their own final score minus the opponent's final score, assuming the opponent does the same.
• Return True if Player 1's final score is greater than or equal to Player 2's under optimal play (a tie counts as a win for Player 1), and False otherwise.

Constraints

• 1 <= len(nums) <= 20
• 0 <= nums[i] <= 10^7

Examples

Example 1

• Input: nums = [2, 9, 4]
• Output: False
• Explanation: Whichever end Player 1 takes, Player 2 can then take 9. Player 1's best total is 6 against 9.

Example 2

• Input: nums = [3, 7, 2, 2]
• Output: True
• Explanation: Player 1 takes the rightmost 2, leaving [3, 7, 2]. Whichever end Player 2 takes, Player 1 can then take 7. Player 1 finishes with 9 against Player 2's 5.

Example 3

• Input: nums = [5]
• Output: True

End-Picking Duel

Two players play a game on a row of non-negative integers nums. They alternate turns, and Player 1 moves first. On each turn, the current player removes either the leftmost or the rightmost remaining number and adds it to their own score. Both scores start at 0, and the game ends when no numbers remain.

Both players play optimally: on every turn, the player to move picks the end that maximizes their own final score minus the opponent's final score, assuming the opponent plays the same way.

Implement first_player_can_win(nums) and return True if Player 1's final score is greater than or equal to Player 2's under optimal play (a tie counts as a win for Player 1), and False otherwise.

Constraints

• 1 <= len(nums) <= 20
• 0 <= nums[i] <= 10^7
• Every total and every score difference is at most 2 * 10^8 in absolute value, so it fits in a signed 32-bit integer.

Example 1

• Input: nums = [2, 9, 4]
• Output: False
• Explanation: Whichever end Player 1 takes, Player 2 can then take 9. Player 1's best total is 6 against 9.

Example 2

• Input: nums = [3, 7, 2, 2]
• Output: True
• Explanation: Player 1 takes the rightmost 2, leaving [3, 7, 2]. Whichever end Player 2 takes, Player 1 can then take 7. Player 1 finishes with 9 against Player 2's 5.

Example 3

• Input: nums = [5]
• Output: True

Hints

1. Always grabbing the larger end is not enough: a small grab now can hand your opponent a much larger number next turn.
2. Whatever moves have been made, the numbers left always form one contiguous block nums[i..j]. What single value about that block would tell the player to move which end to take?
3. Measure a block by the best margin (your total minus your opponent's) the player to move can guarantee on it. After you take one end, your opponent faces a smaller block with the roles swapped.

Approach

After any sequence of moves the remaining numbers are a contiguous block nums[i..j], so the game state is just (i, j). Let diff(i, j) be the largest margin (the mover's future total minus the other player's future total) that the player to move can guarantee on that block. If the mover takes nums[i], the opponent becomes the mover on nums[i+1..j] and gains diff(i+1, j) relative to us, so our margin is nums[i] - diff(i+1, j); taking nums[j] similarly gives nums[j] - diff(i, j-1). The mover picks the larger: diff(i, j) = max(nums[i] - diff(i+1, j), nums[j] - diff(i, j-1)), with diff(i, i) = nums[i]. This is exactly the source's definition of optimal play. Player 1 moves first on the whole row, so the answer is diff(0, n-1) >= 0 (a tie counts as a win). The reference fills the table by increasing block length and keeps one row: when computing length L in increasing i, diff[i] still holds the margin of nums[i..j-1] and diff[i+1] still holds the margin of nums[i+1..j], so both inputs are available before diff[i] is overwritten. Greedy rules such as 'take the larger end' fail: in [3, 7, 3, 2, 3] both ends are 3, but taking the left 3 exposes the 7 and loses, while taking the right 3 leads to a 9-9 tie, so the answer is True. A side note: with an even number of values Player 1 can always force taking every even-indexed or every odd-indexed value, so even-length rows always return True; the DP handles both parities uniformly.

• Time complexity: O(n^2), where n = len(nums)
• Space complexity: O(n)