> ## Documentation Index
> Fetch the complete documentation index at: https://leetcode-py.wisl.dev/llms.txt
> Use this file to discover all available pages before exploring further.

> ## Agent Instructions
> leetcode-py is a Python LeetCode practice environment generator with one CLI: lcpy. It is not a service or platform.
> Each problem is a directory under leetcode/ with README.md, solution.py, test_solution.py, helpers.py, and playground.ipynb. lcpy gen creates them from JSON templates bundled with the package.
> Examples are backed by tests; copy them verbatim.

# Stone Game III Python Solution with Tests

> Tested Python solution for LeetCode 1406 with 18 pytest cases. Generate a practice environment with lcpy.

LeetCode 1406, Hard. Topics: Array, Math, Dynamic Programming, Game Theory. [View on LeetCode](https://leetcode.com/problems/stone-game-iii/description/).

Generate this problem as a practice environment: tested reference solution, 18 [parametrized pytest cases](/practice/testing), and a playground notebook:

```bash theme={"theme":{"light":"github-light","dark":"github-dark"}}
lcpy gen -n 1406   # by problem number
lcpy gen -s stone_game_iii   # by problem name
```

## Problem

Alice and Bob continue their games with piles of stones. There are several stones **arranged in a row**, and each stone has an associated value which is an integer given in the array `stoneValue`.

Alice and Bob take turns, with Alice starting first. On each player's turn, that player can take `1`, `2`, or `3` stones from the **first** remaining stones in the row.

The score of each player is the sum of the values of the stones taken. The score of each player is `0` initially.

The objective of the game is to end with the highest score, and the winner is the player with the highest score and there could be a tie. The game continues until all the stones have been taken.

Assume Alice and Bob **play optimally**.

Return `"Alice"` if Alice will win, `"Bob"` if Bob will win, or `"Tie"` if they will end the game with the same score.

### Examples

```
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.
```

### Constraints

* `1 <= stoneValue.length <= 5 * 10^4`
* `-1000 <= stoneValue[i] <= 1000`

## Solution

Reference implementation from [solution.py on GitHub](https://github.com/wislertt/leetcode-py/blob/main/leetcode/stone_game_iii/solution.py), full suite in [test\_solution.py](https://github.com/wislertt/leetcode-py/blob/main/leetcode/stone_game_iii/test_solution.py):

```python theme={"theme":{"light":"github-light","dark":"github-dark"}}
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"
```

## Complexity

| Time | Space |
| ---- | ----- |
| O(n) | O(n)  |

## Tags

[NeetCode 250](/catalog/neetcode-250), [NeetCode All](/catalog/neetcode).