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

<p>Alice and Bob take turns, with Alice starting first.</p>

<p>On each player&#39;s turn, that player can take <strong>all the stones</strong> in the <strong>first</strong> <code>X</code> remaining piles, where <code>1 &lt;= X &lt;= 2M</code>. Then, we set <code>M = max(M, X)</code>. Initially, M = 1.</p>

<p>The game continues until all the stones have been taken.</p>

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

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">piles = [2,7,9,4,4]</span></p>

<p><strong>Output:</strong> <span class="example-io">10</span></p>

<p><strong>Explanation:</strong></p>

<ul>
	<li>If Alice takes one pile at the beginning, Bob takes two piles, then Alice takes 2 piles again. Alice can get <code>2 + 4 + 4 = 10</code> stones in total.</li>
	<li>If Alice takes two piles at the beginning, then Bob can take all three piles left. In this case, Alice get <code>2 + 7 = 9</code> stones in total.</li>
</ul>

<p>So we return 10 since it&#39;s larger.</p>
</div>

<p><strong class="example">Example 2:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">piles = [1,2,3,4,5,100]</span></p>

<p><strong>Output:</strong> <span class="example-io">104</span></p>
</div>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= piles.length &lt;= 100</code></li>
	<li><code>1 &lt;= piles[i]&nbsp;&lt;= 10<sup>4</sup></code></li>
</ul>

#if 0 // recursive.
class Solution {
    // memo_[i][m] - best score for starting player when i stones have been used and particular m.
    vector<vector<int>> memo_;

public:
    int stoneGameII(vector<int>& piles) {
        const size_t n = piles.size();

        memo_ = vector<vector<int>>(n, vector<int>(n, -1));

        vector<int> prefix_sums(n+1); // prefix_sums[i] is the sum of piles[0..i-1]
        int prev = 0;
        for (size_t i = 0; i < n; ++i) {
            prev += piles[i];
            prefix_sums[i+1] = prev;
        }

        return solve(n, prefix_sums, 0, 1);
    }

private:
    // returns max score for the current player.
    int solve(size_t n, const vector<int>& prefix_sums, int piles_pos, int m) {
        if (piles_pos + m*2 >= n)
            return prefix_sums[n] - prefix_sums[piles_pos]; // taking what's left.

        if (memo_[piles_pos][m] != -1)
            return memo_[piles_pos][m];
        
        int ans = 0;
        for (int x = 1; x <= min<int>(2*m, n - piles_pos); ++x) {
            int best_oppponent_score = solve(n, prefix_sums, piles_pos + x, max(m, x));

            ans = max(ans, prefix_sums[n] - prefix_sums[piles_pos] - best_oppponent_score);
        }

        memo_[piles_pos][m] = ans;

        return ans;
    }
};

#else // simulated recursion.

class Solution {
    // memo_[i][m] - best score for starting player when i stones have been used and particular m.
    vector<vector<int>> memo_;

public:
    int stoneGameII(vector<int>& piles) {
        const size_t n = piles.size();

        memo_ = vector<vector<int>>(n, vector<int>(n, -1));

        vector<int> prefix_sums(n+1); // prefix_sums[i] is the sum of piles[0..i-1]
        int prev = 0;
        for (size_t i = 0; i < n; ++i) {
            prev += piles[i];
            prefix_sums[i+1] = prev;
        }

        return solve(n, prefix_sums);
    }

private:
    struct Context {
        int piles_pos = 0;
        int m = 1;
        int* ret = nullptr;

        int state = 0;
        int x = 1;
        int best_oppponent_score = 0;
    };

    // returns max score for the current player.
    int solve(size_t n, const vector<int>& prefix_sums) {
        stack<Context> st;
        int ans = 0;
        st.push({.piles_pos = 0, .m = 1, .ret = &ans});

        while (!st.empty()) {
            auto& ctx = st.top();

            if (ctx.piles_pos + ctx.m*2 >= n) {
                *ctx.ret = prefix_sums[n] - prefix_sums[ctx.piles_pos];
                st.pop();
                continue;
            }

            if (memo_[ctx.piles_pos][ctx.m] != -1) {
                *ctx.ret = memo_[ctx.piles_pos][ctx.m];
                st.pop();
                continue;
            }

            if (ctx.state == 0) {
                st.push({.piles_pos = ctx.piles_pos + ctx.x, .m = max(ctx.m, ctx.x), .ret = &ctx.best_oppponent_score});
                ctx.state = 1;
            } else if (ctx.state == 1) {
                *ctx.ret = max(*ctx.ret, prefix_sums[n] - prefix_sums[ctx.piles_pos] - ctx.best_oppponent_score);

                ++ctx.x;
                if (ctx.x > min<int>(2*ctx.m, n - ctx.piles_pos)) {
                    memo_[ctx.piles_pos][ctx.m] = *ctx.ret;
                    st.pop();
                    continue;
                }

                ctx.best_oppponent_score = 0;
                st.push({.piles_pos = ctx.piles_pos + ctx.x, .m = max(ctx.m, ctx.x), .ret = &ctx.best_oppponent_score});
            }
        }

        return ans;
    }

    int solve_rec(size_t n, const vector<int>& prefix_sums, int piles_pos = 0, int m = 1) {
        if (piles_pos + m*2 >= n)
            return prefix_sums[n] - prefix_sums[piles_pos]; // taking what's left.

        if (memo_[piles_pos][m] != -1)
            return memo_[piles_pos][m];
        
        int ans = 0;
        for (int x = 1; x <= min<int>(2*m, n - piles_pos); ++x) {
            int best_oppponent_score = solve_rec(n, prefix_sums, piles_pos + x, max(m, x));

            ans = max(ans, prefix_sums[n] - prefix_sums[piles_pos] - best_oppponent_score);
        }

        memo_[piles_pos][m] = ans;

        return ans;
    }
};

#endif

28191