1
class Solution(object):
2
    def stoneGameIII(self, stoneValue):
3
        """
4
        :type stoneValue: List[int]
5
        :rtype: str
6
        """
7
        n = len(stoneValue)
8
        suffixSum = [0 for _ in range(n + 1)]
9
        dp = [0 for _ in range(n + 1)]
10
        for i in range(n - 1, -1, -1):
11
            suffixSum[i] = suffixSum[i + 1] + stoneValue[i]
12
        for i in range(n - 1, -1, -1):
13
            dp[i] = stoneValue[i] + suffixSum[i + 1] - dp[i + 1]
14
            for k in range(i + 1, min(n, i + 3)):
15
                dp[i] = max(dp[i], suffixSum[i] - dp[k + 1])
16
        if dp[0] * 2 == suffixSum[0]:
17
            return "Tie"
18
        elif dp[0] * 2 > suffixSum[0]:
19
            return "Alice"
20
        else:
21
            return "Bob"