<p>There are several stones <strong>arranged in a row</strong>, and each stone has an associated value which is an integer given in the array <code>stoneValue</code>.</p>

<p>In each round of the game, Alice divides the row into <strong>two non-empty rows</strong> (i.e. left row and right row), then Bob calculates the value of each row which is the sum of the values of all the stones in this row. Bob throws away the row which has the maximum value, and Alice&#39;s score increases by the value of the remaining row. If the value of the two rows are equal, Bob lets Alice decide which row will be thrown away. The next round starts with the remaining row.</p>

<p>The game ends when there is only <strong>one stone remaining</strong>. Alice&#39;s is initially <strong>zero</strong>.</p>

<p>Return <i>the maximum score that Alice can obtain</i>.</p>

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

<pre>
<strong>Input:</strong> stoneValue = [6,2,3,4,5,5]
<strong>Output:</strong> 18
<strong>Explanation:</strong> In the first round, Alice divides the row to [6,2,3], [4,5,5]. The left row has the value 11 and the right row has value 14. Bob throws away the right row and Alice&#39;s score is now 11.
In the second round Alice divides the row to [6], [2,3]. This time Bob throws away the left row and Alice&#39;s score becomes 16 (11 + 5).
The last round Alice has only one choice to divide the row which is [2], [3]. Bob throws away the right row and Alice&#39;s score is now 18 (16 + 2). The game ends because only one stone is remaining in the row.
</pre>

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

<pre>
<strong>Input:</strong> stoneValue = [7,7,7,7,7,7,7]
<strong>Output:</strong> 28
</pre>

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

<pre>
<strong>Input:</strong> stoneValue = [4]
<strong>Output:</strong> 0
</pre>

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

<ul>
	<li><code>1 &lt;= stoneValue.length &lt;= 500</code></li>
	<li><code>1 &lt;= stoneValue[i] &lt;= 10<sup>6</sup></code></li>
</ul>

class Solution:
    def stoneGameV(self, stoneValue: List[int]) -> int:
        def getPartialSum():
            for i in range(n):
                partial_sum[i][i] = stoneValue[i]
            for i in range(n):
                for j in range(i+1, n):
                    partial_sum[i][j] = partial_sum[i][j-1]+stoneValue[j]
                               
        # (O(n) search)    
        def preCalCutIdx():
            # based on the fact that cut index is increasing with k for 
            # partial_sum[start][k]
            for i in range(n-1):
                cp = i
                cut_index[i][i+1] = i
                for j in range(i+2, n):
                    while cp < j-1 and partial_sum[i][cp] < partial_sum[cp+1][j]:
                        cp += 1  
                    cut_index[i][j] = cp
		
			
        @lru_cache(None)
        def dfs(start, end):
            if start >= end:
                return 0
            max_score = 0
            # find first cut s.t. left sum >= right sum 
            cut = cut_index[start][end]
            # we can't find cut s.t. left sum >= right sum
            if cut == -1:
                cut = end-1
            sum1 = partial_sum[start][cut]
            sum2 = partial_sum[cut+1][end]
            if sum1 < sum2:
                # calcuate left[start][cut] if not yet
                dfs(start, cut)
                # the remaining will be the left part for sure, no 
                # matter where the cut is. 
                max_score = left[start][cut]
            elif sum1 == sum2:
                dfs(start, cut)
                dfs(cut+1, end)
                # if real cut in the range of [cut+1, end], remaining will be the right part
                # if real cut in the range of [0, cut], remaing will be the left part
                # if real cut is cut, either can be the remaining. 
                max_score = max(left[start][cut], right[cut+1][end])
            else:
                dfs(cut+1, end)
                # we are selecting the cut in the range of [cut, end] having 
                # the max score. For cut in that range, the remaining is 
                # the right part of the cut for sure. 
                max_score = right[cut+1][end]
                if cut > start:
                    dfs(start, cut-1)
                    # we are selecting the cut in the range of [0, cut] having 
                    # the max score. The remaining is the left part for sure. 
                    max_score = max(max_score, left[start][cut-1])
            dfs(start, end-1)
            dfs(start+1, end)
            # updating left and right arrays. 
            left[start][end] = max(left[start][end-1], partial_sum[start][end]+max_score)
            right[start][end] = max(right[start+1][end], partial_sum[start][end]+max_score)
            return max_score
            
        n = len(stoneValue)
        partial_sum = [[0]*n for _ in range(n)]
        cut_index = [[-1]*n for _ in range(n)]
        # left[i][j]: cut in the range of [i, j], max score of left part
        # right[i][j]: cut in the range of [i, j], max score of right part
        left = [[0]*n for _ in range(n)]
        right = [[0]*n for _ in range(n)]
        for i in range(n):
            left[i][i] = stoneValue[i]
            right[i][i] = stoneValue[i]
        getPartialSum()
        # for partial_sum[i][j], find cut index between i and j 
        # s.t partial_sum[i][cut_index] >= partial_sum[cut_index+1][j] or 
        # cut_index = j-1 if not exist. 
        preCalCutIdx()
        return dfs(0, n-1)
99100