486. Predict the Winner

Link

Same as 877, but care about the return condition(could be odd array)

class Solution:
    def PredictTheWinner(self, nums: List[int]) -> bool:

        n = len(nums)

        if n <= 2:
            return True

        @cache
        def backtrack(i, j):
            if i == j:
                return nums[i]
            if j - i + 1 == 2:
                return max(nums[i], nums[j])

            c = 0

            c = max(c, nums[i] + min(backtrack(i+2, j), backtrack(i+1, j-1)))
            c = max(c, nums[j] + min(backtrack(i, j-2), backtrack(i+1, j-1)))

            return c

        return backtrack(0, n-1) * 2 >= sum(nums)