Stone Game III Python Solution with Tests

lcpy gen -n 1406   # by problem number
lcpy gen -s stone_game_iii   # by problem name

Input: stoneValue = [1,2,3,7]
Output: "Bob"
Explanation: Alice will always lose. Her best move will be to take three piles and the score become 6. Now the score of Bob is 7 and Bob wins.

Input: stoneValue = [1,2,3,-9]
Output: "Alice"
Explanation: Alice must choose all the three piles at the first move to win and leave Bob with negative score.

Input: stoneValue = [1,2,3,6]
Output: "Tie"
Explanation: Alice cannot win this game. She can end the game in a draw if she decided to choose all the first three piles, otherwise she will lose.

class Solution:
    # Time: O(n)
    # Space: O(n)
    def stone_game_iii(self, stone_value: list[int]) -> str:
        n = len(stone_value)

        # dp[i] = best score advantage the player to move can build over the
        # opponent from stone_value[i:] (positive => current player leads).
        dp = [0] * (n + 1)
        for i in range(n - 1, -1, -1):
            best = -(10**18)
            taken = 0
            for x in range(i, min(i + 3, n)):
                taken += stone_value[x]
                # Current pockets `taken`, then opponent enjoys dp[x + 1].
                best = max(best, taken - dp[x + 1])
            dp[i] = best

        if dp[0] > 0:
            return "Alice"
        if dp[0] < 0:
            return "Bob"
        return "Tie"