Predict the Winner

Intuition

Instead of tracking both players' scores separately, it is cleaner to track a single quantity: the margin by which the player to move can beat the other player on a given subarray. Let dp[i][j] be that best margin over nums[i..j]. If the current player takes nums[i], they gain nums[i] and then face dp[i+1][j] from the opponent's perspective, which counts against them, so this option is worth nums[i] - dp[i+1][j]. Taking nums[j] is symmetrically worth nums[j] - dp[i][j-1]. The current player chooses the larger of the two, and a single-element range simply yields that element as the margin. Player 1 can guarantee at least a tie exactly when dp[0][n-1] is non-negative.

Algorithm walkthrough

1. 1Set dp[i][i] = nums[i]: with one element the current player takes it and leads by that amount.
2. 2Process subarrays in order of increasing length so shorter ranges are ready before longer ones.
3. 3For range i..j, taking the left end is worth nums[i] - dp[i+1][j].
4. 4Taking the right end is worth nums[j] - dp[i][j-1]; assign dp[i][j] the maximum of the two options.
5. 5The value dp[0][n-1] is Player 1's optimal margin over the whole array.
6. 6Return true when that margin is at least zero, since a tie counts as a Player 1 win.

Implementation

class Solution:
    def predictTheWinner(self, nums: List[int]) -> bool:
        n = len(nums)
        dp = [[0] * n for _ in range(n)]
        for i in range(n):
            dp[i][i] = nums[i]
        for length in range(2, n + 1):
            for i in range(0, n - length + 1):
                j = i + length - 1
                take_left = nums[i] - dp[i + 1][j]
                take_right = nums[j] - dp[i][j - 1]
                dp[i][j] = max(take_left, take_right)
        return dp[0][n - 1] >= 0