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

class Solution:
    def stoneGameII(self, piles: List[int]) -> int:
        cache = {}

        subsumsOfPiles = []
        currentSum = 0
        for pile in piles:
            currentSum += pile
            subsumsOfPiles.append(currentSum)

        def getSubsum(left: int, right: int):
            if (left - 1 < 0):
                return subsumsOfPiles[right - 1]

            return subsumsOfPiles[right - 1] - subsumsOfPiles[left - 1]

        def dpFunc(aliceCurrentPileIndex: int, m: int):
            if ((aliceCurrentPileIndex, m) in cache):
                return cache[(aliceCurrentPileIndex, m)]
            if aliceCurrentPileIndex >= len(piles):
                cache[(aliceCurrentPileIndex, m)] = 0
                return 0
            
            maxVal = 0
            
            topOfIRange = 2*m + 1
            for i in range(1, topOfIRange):
                if (aliceCurrentPileIndex + i - 1 >= len(piles)):
                    break

                newEnemyM = max(m, i)
                bobNewPileIndex = aliceCurrentPileIndex + i

                # Bob Turn
                minVal = float("inf")
                minValPileIndex = 0
                minValJ = 1

                topOfJRange = 2*newEnemyM + 1
                for j in range(1, topOfJRange):
                    newBobVal = dpFunc(aliceCurrentPileIndex=bobNewPileIndex+j, m=max(j, newEnemyM))
                    if (newBobVal < minVal):
                        minVal = newBobVal
                        minValPileIndex = bobNewPileIndex + j
                        minValJ = j

                newAliceM = max(newEnemyM, minValJ)

                maxVal = max(
                    maxVal,
                    dpFunc(
                        aliceCurrentPileIndex=minValPileIndex,
                        m=newAliceM
                    ) + (
                        getSubsum(aliceCurrentPileIndex, aliceCurrentPileIndex + i)
                    )
                )

            cache[(aliceCurrentPileIndex, m)] = maxVal
            return maxVal

        output = dpFunc(aliceCurrentPileIndex=0, m=1)
        return output
        
20100