<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>
class Solution:
    def stoneGameVIII(self, stones: List[int]) -> int:
        # Tried a kind of obvious dfs(leftStone, i) that iterated over all possible i..j ranges the current player can take
        # Correct answers but WAY too slow.

        # for  A B C D E

        # example game:
        #    Alice: takes AB. AB,0,  AB C D E
        #      Bob: takes ABCD. AB, ABCD,  ABCD E
        #        Alice: takes ABCDE. AB+ABCDE, ABCD
        #          final score difference: ABE (so just what Alice took)
        #
        # observation: last person scores the sum of the whole array
        # current player, if they take i..j, scores the sum of 0..j because all prior stones were prepended

        #     current player takes i: scores acc[i]
        #         other player will play to maximize score difference on i+1 onward
        #         such that the current player will score acc[i]-bestDiff[i+1]
        #     current player takes i..i+1: scores acc[i+1], other player scores bestDiff[i+2]
        #         so scoreDifference is acc[i+1]-bestDiff[i+2]
        #     etc.
        #       so it's a max over acc[j]-bestDiff[j+1] for all j < N-1, plus the case where the current player takes all: sum of array
        # We fill in the table going backwards because we need bestDiff[j] for j > i

        # in-place transform of stones to accumulated values
        N = len(stones)
        for i in range(1, N): stones[i] += stones[i-1]

        # # edge case: for last element our only option is to take it, there's no later turn.
        # # thus the current player has taken all of the values
        # bestDiff = [0]*N
        # bestDiff[-1] = stones[-1] # last stone: must take, score is sum of all stones

        # for i in range(N-2, 0, -1): # end iteration at 1 because first person must take at least 0..1
        #     # person at i can take ..i: acc[i] - bestDiff[i+1]
        #     #                     ..i+1: acc[i+1] - bestDiff[i+2]
        #     #                     ... acc[N-1] - 0 # edge case: game over, no later turn for N-2, so handle this separately
        #     bestDiff[i] = stones[-1] # current player can just take all the remaining stones
        #     for j in range(i, N-1):
        #         # or they can take 0..j, and suffer the other person's best over j+1..
        #         bestDiff[i] = max(bestDiff[i], stones[j]-bestDiff[j+1])

        # return bestDiff[1]

        # ## So two new observations:
        # #   1. bestDiff[i] is the best answer we can get if the current player takes stones through at least i
        # #   2. based on this description, and the loop, we note that the cumulative max adds a single new term each time
        # #      for i, the new term is stones[i]-bestDiff[i+1]
        # #      So we can replace this with a cumulative sum!

        #### So redo with the O(1) space
        best = stones[-1] # best score if current player takes through i+1 or later; for N-2 the only later move is N-1, i.e. taking all
        for i in range(N-2, 0, -1): # end loop at 1 because Alice must take at least two stones, indices 0 and 1
            # current player has two options:
            #    > if they take stones through i only, then
            #        > current player scores stones[i] (we accumulated in place)
            #        > opponent takes through i+1 at least, scoring best
            #        > total score difference is stones[i] - best
            #    > or we can take through stones i+1 or later, scoring best
            best = max(
                stones[i] - best, # take 0..i, opponent takes best on i+1..
                best)             # take something in i+1, we already have cumulative best score

        return best
784