class Solution:
    def PredictTheWinner(self, nums: List[int]) -> bool:
        n = len(nums)
        # dp[i] will eventually store the max diff for subarray ending at index j
        # initialized with the base case (subarrays of length 1)
        dp = nums[:] 
        
        # Iterate over the length of the subarray
        # diff is the distance between left pointer (i) and right pointer (j)
        for diff in range(1, n):
            for i in range(n - diff):
                j = i + diff
                # Update dp[i] for the new range [i, j]
                # dp[i+1] represents the result of range [i+1, j] (after picking left)
                # dp[i] (old value) represents the result of range [i, j-1] (after picking right)
                pick_left = nums[i] - dp[i + 1]
                pick_right = nums[j] - dp[i]
                
                dp[i] = max(pick_left, pick_right)
        
        return dp[0] >= 0