<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>

from functools import cache
class Solution:
    def stoneGameII(self, piles: List[int]) -> int:
        # @cache
        # def max_win(j, M):
        #     if j + 2 * M >= len(piles):
        #         # print(j, M, sum(piles[j: ]), "A")
        #         return sum(piles[j: ])

        #     curr_sum = 0
        #     best_outcome = float('-inf')
        #     for k in range(j, j + 2 * M):
        #         curr_sum += piles[k]
        #         best_outcome = max(best_outcome,\
        #         curr_sum - max_win(k + 1, max(M, k - j + 1)))

        #     # print(j, M, best_outcome)
        #     return best_outcome

        # return (max_win(0, 1) + sum(piles)) // 2



        l = len(piles)

        prefix_sum = [0] + piles[:]
        for j in range(1, l + 1):
            prefix_sum[j] += prefix_sum[j - 1]

        @cache
        def dp(i, M):
        
            if i + 2 * M > l - 1:
                return [prefix_sum[-1] - prefix_sum[i] , 0]
            
            new_M = M
            max_gain = 0
            gain_other = 0
            for X in range(1, 2 * M + 1):

                new_M = max(M, X)
                gain = prefix_sum[i + X] - prefix_sum[i] + dp(i + X, new_M)[1]
                if gain > max_gain:
                    max_gain = gain
                    gain_other = dp(i + X, new_M)[0]

            return [max_gain, gain_other]
        
        return dp(0, 1)[0]

19800