1
# Runtime: 6869 ms (Top 56.16%) | Memory: 13.9 MB (Top 96.15%)
2
class Solution:
3
    def stoneGameVII(self, S: List[int]) -> int:
4
        N, dp = len(S), [0] * len(S)
5
        for i in range(N - 2, -1, -1):
6
            total = S[i]
7
            for j in range(i + 1, N):
8
                total += S[j]
9
                dp[j] = max(total - S[i] - dp[j], total - S[j] - dp[j - 1])
10
        return dp[-1]