Problem statement

https://binarysearch.com/problems/Candy-Race-Sequel/

Solution

Equal to Leetcode 1406. Stone Game III.

Complexity

It is O(n) for time and space.

Code

class Solution:
    def solve(self, A):
        @lru_cache(None)
        def dp(i):
            if i == n: return 0
            ans, last = -float("inf"), 0
            for j in range(i, min(i+3, n)):
                last += A[j]
                ans = max(ans, last - dp(j + 1))
            return ans
            
        n = len(A)
        return dp(0) > 0