// 演算法 / Algorithm: 動態規劃 + 記憶化 (DP with memoization).
// 狀態 dp(i,m) = 剩 piles[i:]、M=m 時，「輪到的人」最多能拿的石頭。
// 零和賽局：我拿的 = 剩下總和 suffix[i] − 對手能拿的 dp(...)。答案 = dp(0,1)。
// State dp(i,m) = best stones the mover can get from piles[i:] with M=m;
// zero-sum so mine = suffix[i] − opponent's dp(...). Answer = dp(0,1).

static int n;               // 石堆數量 / number of piles
static int suffix[101];     // suffix[i] = piles[i..n-1] 的總和 / suffix sum from i
static int memo[101][101];  // memo[i][m]：算過的答案，-1 表示還沒算 / cached dp, -1 = unset

// 回傳「輪到的人」在狀態 (i,m) 能拿到的最多石頭
// Returns max stones the current mover can secure at state (i,m)
static int dp(int i, int m) {
    if (i >= n) return 0;                 // 沒石頭可拿 / nothing left to take
    if (i + 2 * m >= n)                   // 這步就能把剩下全拿光 / can take all remaining now
        return suffix[i];                 // 全拿 = 剩下總和 / grabbing all = suffix sum
    if (memo[i][m] != -1)                 // 這個狀態算過了 / already solved this state
        return memo[i][m];                // 直接回傳快取 / return cached value

    int best = 0;                         // 目前找到的最大所得 / best take found so far
    // 枚舉這一步拿 X 堆 / try taking X piles this turn, X from 1 to 2m
    for (int x = 1; x <= 2 * m; x++) {
        int nm = (m > x) ? m : x;         // 新的 M = max(m, x) / updated M after taking x
        // 我拿走 piles[i..i+x-1]，對手在 (i+x, nm) 拿 dp()，剩下歸我
        // I take piles[i..i+x-1]; opponent gets dp(i+x,nm); the rest is mine
        int taken = suffix[i] - dp(i + x, nm);
        if (taken > best) best = taken;   // 更新最佳值 / keep the largest
    }
    memo[i][m] = best;                    // 存入快取 / store into cache
    return best;
}

int stoneGameII(int* piles, int pilesSize) {
    n = pilesSize;                        // 記下堆數 / record number of piles
    suffix[n] = 0;                        // 邊界：終點之後總和為 0 / sentinel: sum past the end is 0
    // 由後往前累加，算出每個後綴和 / build suffix sums right-to-left
    for (int i = n - 1; i >= 0; i--)
        suffix[i] = suffix[i + 1] + piles[i];
    // 把整張記憶化表清成 -1（未算） / reset the whole memo table to -1 (unset)
    for (int i = 0; i <= n; i++)
        for (int j = 0; j <= n; j++)
            memo[i][j] = -1;
    return dp(0, 1);                      // 從頭開始、M=1，求 Alice 的最佳所得 / start at i=0, M=1
}