// 演算法 / Algorithm: 與 C 版相同的 DP 記憶化 (same memoized DP as the C version).
// dp(i,m) = 剩 piles[i:]、M=m 時輪到的人最多能拿；零和 → mine = suffix[i] − dp(next)。
// dp(i,m) = best the mover can secure from piles[i:] with M=m; answer = dp(0,1).
#include <vector>
#include <algorithm>   // std::max
using namespace std;

class Solution {
    int n;                              // 堆數 / number of piles
    vector<int> suffix;                 // 後綴和 / suffix sums
    vector<vector<int>> memo;           // memo[i][m]，-1 = 未算 / cache, -1 = unset

    int dp(int i, int m) {
        if (i >= n) return 0;                    // 沒石頭 / nothing left
        if (i + 2 * m >= n) return suffix[i];    // 能一次拿光 → 全拿 / take everything remaining
        int &cached = memo[i][m];                // 用參考指向該格，寫回更方便 / reference to the cell
        if (cached != -1) return cached;         // 已算過就回傳 / return if already solved

        int best = 0;                            // 最佳所得 / best take
        for (int x = 1; x <= 2 * m; ++x) {       // 嘗試拿 x 堆 / try taking x piles
            // max(m,x) 更新 M；suffix[i]−dp(...) 是我這條路線能拿的
            // max(m,x) updates M; suffix[i]−dp(...) is my take on this branch
            best = max(best, suffix[i] - dp(i + x, max(m, x)));
        }
        return cached = best;                    // 存入快取並回傳 / cache and return
    }

public:
    int stoneGameII(vector<int>& piles) {
        n = piles.size();                        // 記下堆數 / record size
        suffix.assign(n + 1, 0);                 // 大小 n+1、全填 0（含哨兵）/ size n+1, all zero
        // 由右往左建後綴和 / build suffix sums from right to left
        for (int i = n - 1; i >= 0; --i)
            suffix[i] = suffix[i + 1] + piles[i];
        // (n+1)×(n+1) 的表全初始化為 -1 / init an (n+1)×(n+1) table to -1
        memo.assign(n + 1, vector<int>(n + 1, -1));
        return dp(0, 1);                         // i=0, M=1 開局 / start the game
    }
};