"""
p79 — Stone Game II (LeetCode 1140, Medium-Hard).

Game DP from current-player POV.
State: (i, M); piles[i..n-1] remaining; current player may take x in 1..2M front piles;
then M = max(M, x); opponent's turn.

Suffix-sum identity:
    my_total_from(i, M) = suf[i] - opponent_optimal_from(i+x, max(M, x))
=>  dp[i][M] = max over x in 1..min(2M, n-i) of (suf[i] - dp[i+x][max(M, x)])

Base: i == n -> 0; 2M >= n - i -> take everything (suf[i]).
Answer: dp[0][1].
"""
from __future__ import annotations
import random
from functools import lru_cache
from typing import List


def stone_game_ii_dp(piles: List[int]) -> int:
    n = len(piles)
    suf = [0] * (n + 1)
    for i in range(n - 1, -1, -1):
        suf[i] = suf[i + 1] + piles[i]
    # dp[i][M]: i in 0..n, M in 1..n. Cap M at n.
    dp = [[0] * (n + 2) for _ in range(n + 1)]
    for i in range(n - 1, -1, -1):
        for M in range(n, 0, -1):
            if 2 * M >= n - i:
                dp[i][M] = suf[i]
            else:
                best = 0
                for x in range(1, 2 * M + 1):
                    cand = suf[i] - dp[i + x][min(n, max(M, x))]
                    if cand > best:
                        best = cand
                dp[i][M] = best
    return dp[0][1]


def stone_game_ii_memo(piles: List[int]) -> int:
    n = len(piles)
    suf = [0] * (n + 1)
    for i in range(n - 1, -1, -1):
        suf[i] = suf[i + 1] + piles[i]

    @lru_cache(maxsize=None)
    def solve(i: int, M: int) -> int:
        if i >= n:
            return 0
        if 2 * M >= n - i:
            return suf[i]
        best = 0
        for x in range(1, 2 * M + 1):
            cand = suf[i] - solve(i + x, max(M, x))
            if cand > best:
                best = cand
        return best

    return solve(0, 1)


def stone_game_ii_brute(piles: List[int]) -> int:
    # Recursive minimax without memo. Returns current-player optimal from (i, M).
    n = len(piles)

    def solve(i: int, M: int) -> int:
        if i >= n:
            return 0
        best = 0
        taken = 0
        for x in range(1, 2 * M + 1):
            if i + x - 1 >= n:
                # take whatever is left
                pass
            cap = min(x, n - i)
            taken_now = sum(piles[i:i + cap])
            opp = solve(i + cap, max(M, x))
            rest_total = sum(piles[i + cap:])
            my = taken_now + (rest_total - opp)
            if my > best:
                best = my
            if cap < x:
                break  # already took all remaining
            _ = taken
        return best

    return solve(0, 1)


def edge_cases() -> None:
    assert stone_game_ii_dp([2, 7, 9, 4, 4]) == 10
    assert stone_game_ii_memo([2, 7, 9, 4, 4]) == 10
    assert stone_game_ii_brute([2, 7, 9, 4, 4]) == 10
    assert stone_game_ii_dp([1, 2, 3, 4, 5, 100]) == 104
    assert stone_game_ii_dp([1]) == 1
    assert stone_game_ii_dp([5, 5]) == 10  # 2M=2 >= n=2; take all
    print("edge_cases: PASS")


def stress_test() -> None:
    rng = random.Random(42)
    for trial in range(200):
        n = rng.randint(1, 7)
        piles = [rng.randint(1, 20) for _ in range(n)]
        a = stone_game_ii_dp(piles)
        b = stone_game_ii_memo(piles)
        c = stone_game_ii_brute(piles)
        assert a == b == c, f"trial {trial}: piles={piles} dp={a} memo={b} brute={c}"
    print("stress_test: 200 trials — iterative DP, memoized, brute minimax all agree.")


if __name__ == "__main__":
    edge_cases()
    stress_test()
    print("ALL TESTS PASSED")