> ## 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 II Python Solution with Tests

> Tested Python solution for LeetCode 1140 with 16 pytest cases. Generate a practice environment with lcpy.

LeetCode 1140, Medium. Topics: Array, Math, Dynamic Programming, Prefix Sum, Game Theory. [View on LeetCode](https://leetcode.com/problems/stone-game-ii/description/).

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

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

## Problem

Alice and Bob continue their games with piles of stones. There are a number of piles **arranged in a row**, and each pile has a positive integer number of stones `piles[i]`. The objective of the game is to end with the most stones.

Alice and Bob take turns, with Alice starting first.

On each player's turn, that player can take **all the stones** in the **first** `X` remaining piles, where `1 <= X <= 2M`. Then, we set `M = max(M, X)`. Initially, M = 1.

The game continues until all the stones have been taken.

Assuming Alice and Bob play optimally, return the maximum number of stones Alice can get.

### Examples

```
Input: piles = [2,7,9,4,4]
Output: 10
Explanation:
If Alice takes one pile at the beginning, Bob takes two piles, then Alice takes 2 piles again. Alice can get 2 + 4 + 4 = 10 stones in total.
If Alice takes two piles at the beginning, then Bob can take all three piles left. In this case, Alice get 2 + 7 = 9 stones in total.
So we return 10 since it's larger.
```

```
Input: piles = [1,2,3,4,5,100]
Output: 104
```

### Constraints

* `1 <= piles.length <= 100`
* `1 <= piles[i] <= 10^4`

## Solution

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

```python theme={"theme":{"light":"github-light","dark":"github-dark"}}
class Solution:
    # Time: O(n^3) — n start indexes, n M values, up to 2M=2n X picks
    # Space: O(n^2) memo
    def stone_game_ii(self, piles: list[int]) -> int:
        n = len(piles)

        # suffix[i] = total stones in piles[i:]; lets the current player value
        # a move as suffix[i] - opponent_best_from_remaining.
        suffix = [0] * (n + 1)
        for i in range(n - 1, -1, -1):
            suffix[i] = suffix[i + 1] + piles[i]

        memo: dict[tuple[int, int], int] = {}

        def best_from(i: int, m: int) -> int:
            # Max stones the player to move can collect from piles[i:] with bound M=m.
            if i >= n:
                return 0
            # Can take all remaining piles in one move.
            if i + 2 * m >= n:
                return suffix[i]
            if (i, m) in memo:
                return memo[(i, m)]

            best = 0
            for x in range(1, 2 * m + 1):
                if i + x > n:
                    break
                taken = suffix[i] - suffix[i + x]
                opponent = best_from(i + x, max(m, x))
                best = max(best, taken + (suffix[i + x] - opponent))
            memo[(i, m)] = best
            return best

        return best_from(0, 1)
```

## Complexity

| Time                                                      | Space       |
| --------------------------------------------------------- | ----------- |
| O(n^3) — n start indexes, n M values, up to 2M=2n X picks | O(n^2) memo |

## Tags

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