<p>Alice and Bob take turns playing a game, with <strong>Alice starting first</strong>.</p>

<p>There are <code>n</code> stones arranged in a row. On each player&#39;s turn, while the number of stones is <strong>more than one</strong>, they will do the following:</p>

<ol>
	<li>Choose an integer <code>x &gt; 1</code>, and <strong>remove</strong> the leftmost <code>x</code> stones from the row.</li>
	<li>Add the <strong>sum</strong> of the <strong>removed</strong> stones&#39; values to the player&#39;s score.</li>
	<li>Place a <strong>new stone</strong>, whose value is equal to that sum, on the left side of the row.</li>
</ol>

<p>The game stops when <strong>only</strong> <strong>one</strong> stone is left in the row.</p>

<p>The <strong>score difference</strong> between Alice and Bob is <code>(Alice&#39;s score - Bob&#39;s score)</code>. Alice&#39;s goal is to <strong>maximize</strong> the score difference, and Bob&#39;s goal is the <strong>minimize</strong> the score difference.</p>

<p>Given an integer array <code>stones</code> of length <code>n</code> where <code>stones[i]</code> represents the value of the <code>i<sup>th</sup></code> stone <strong>from the left</strong>, return <em>the <strong>score difference</strong> between Alice and Bob if they both play <strong>optimally</strong>.</em></p>

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

<pre>
<strong>Input:</strong> stones = [-1,2,-3,4,-5]
<strong>Output:</strong> 5
<strong>Explanation:</strong>
- Alice removes the first 4 stones, adds (-1) + 2 + (-3) + 4 = 2 to her score, and places a stone of
  value 2 on the left. stones = [2,-5].
- Bob removes the first 2 stones, adds 2 + (-5) = -3 to his score, and places a stone of value -3 on
  the left. stones = [-3].
The difference between their scores is 2 - (-3) = 5.
</pre>

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

<pre>
<strong>Input:</strong> stones = [7,-6,5,10,5,-2,-6]
<strong>Output:</strong> 13
<strong>Explanation:</strong>
- Alice removes all stones, adds 7 + (-6) + 5 + 10 + 5 + (-2) + (-6) = 13 to her score, and places a
  stone of value 13 on the left. stones = [13].
The difference between their scores is 13 - 0 = 13.
</pre>

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

<pre>
<strong>Input:</strong> stones = [-10,-12]
<strong>Output:</strong> -22
<strong>Explanation:</strong>
- Alice can only make one move, which is to remove both stones. She adds (-10) + (-12) = -22 to her
  score and places a stone of value -22 on the left. stones = [-22].
The difference between their scores is (-22) - 0 = -22.
</pre>

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

<ul>
	<li><code>n == stones.length</code></li>
	<li><code>2 &lt;= n &lt;= 10<sup>5</sup></code></li>
	<li><code>-10<sup>4</sup> &lt;= stones[i] &lt;= 10<sup>4</sup></code></li>
</ul>
from typing import List
import sys
sys.setrecursionlimit(10**6)

class Solution:

    def helper(self, stones: List[int], turn: bool) -> int:
        n = len(stones)
        if len(stones) <= 1:
            return 0
        if turn:
            # print("Alice turn:")
            # print("stones:", stones)
            res = float('-inf')
            val = stones[0]
            for i in range(2, len(stones)+1):
                val += stones[i-1]
                new_stones = stones[i:].copy()
                new_stones.insert(0, val)
                # print("  val:", val, "new_stones:", new_stones)
                res = max(res, val + self.helper(new_stones, not turn))
            return res
        else:
            # print("    Bob turn:")
            # print("    stones:", stones)
            res = float('inf')
            val = stones[0]
            for i in range(2, len(stones)+1):
                val += stones[i-1]
                new_stones = stones[i:].copy()
                new_stones.insert(0, val)
                # print("      val:", val, "new_stones:", new_stones)
                res = min(res, -val + self.helper(new_stones, not turn))
            return res
            

    # memoized version, about O(n^2) time complexity due to the
    # fact that we call the helper function starting from the
    # smallest possible gather. I think that if we change it
    # to using the largest possible gather, we can reduce the
    # time complexity a fair bit.
    def stoneGameVIIIMemo(self, stones: List[int]) -> int:
        n = len(stones)
        memo = {}
        def gameHelper(turn: bool, i: int) -> int:
            if i >= n-1:
                return 0
            if (turn, i, stones[i]) in memo:
                return memo[(turn, i, stones[i])]

            if turn:
                # print("Alice turn:")
                # print("stones:", stones[i:])
                res = float('-inf')
                val = stones[i]
                for j in range(i+1, n):
                    old = stones[j]
                    val += old
                    stones[j] = val
                    # print("  val:", val, "new_stones:", stones[j:])
                    res = max(res, val + gameHelper(not turn, j))
                    stones[j] = old

                memo[(turn, i, stones[i])] = res
                return res
            
            else:
                # print("    Bob turn:")
                # print("    stones:", stones[i:])
                res = float('inf')
                val = stones[i]
                for j in range(i+1, n):
                    old = stones[j]
                    val += old
                    stones[j] = val
                    # print("      val:", val, "new_stones:", stones[j:])
                    res = min(res, -val + gameHelper(not turn, j))
                    stones[j] = old
                
                memo[(turn, i, stones[i])] = res
                return res
                    

        score = gameHelper(True, 0)
        return score    
    
    def stoneGameVIII(self, stones: List[int]) -> int:
        n = len(stones)
        memo = {}
        for i in range(1, n):
            stones[i] += stones[i-1]
        
        def recursive(i: int, prefix: List[int], turn: bool) -> int:
            if i == (len(prefix) - 1):
                return prefix[i] if turn else -prefix[i]
            if (i, turn) in memo:
                return memo[(i, turn)]
            
            if turn:
                # Alice's turn
                # we can either take the current prefix and switch turn to Bob or go to the next
                # prefix and keep the turn with Alice
                # Alice is trying to maximize the score
                memo[(i, turn)] = max(recursive(i+1, prefix, turn), prefix[i] + recursive(i+1, prefix, not turn))
            else:
                # Bob's turn
                # we can either take the current prefix and switch turn to Alice or go to the next
                # prefix and keep the turn with Bob
                # Bob is trying to minimize the score
                memo[(i, turn)] = min(recursive(i+1, prefix, turn), -prefix[i] + recursive(i+1, prefix, not turn))
            return memo[(i, turn)]

        return recursive(1, stones, True)
    
245600