<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, they can <strong>remove</strong> either the leftmost stone or the rightmost stone from the row and receive points equal to the <strong>sum</strong> of the remaining stones&#39; values in the row. The winner is the one with the higher score when there are no stones left to remove.</p>

<p>Bob found that he will always lose this game (poor Bob, he always loses), so he decided to <strong>minimize the score&#39;s difference</strong>. Alice&#39;s goal is to <strong>maximize the difference</strong> in the score.</p>

<p>Given an array of integers <code>stones</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>difference</strong> in Alice and Bob&#39;s score 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 = [5,3,1,4,2]
<strong>Output:</strong> 6
<strong>Explanation:</strong> 
- Alice removes 2 and gets 5 + 3 + 1 + 4 = 13 points. Alice = 13, Bob = 0, stones = [5,3,1,4].
- Bob removes 5 and gets 3 + 1 + 4 = 8 points. Alice = 13, Bob = 8, stones = [3,1,4].
- Alice removes 3 and gets 1 + 4 = 5 points. Alice = 18, Bob = 8, stones = [1,4].
- Bob removes 1 and gets 4 points. Alice = 18, Bob = 12, stones = [4].
- Alice removes 4 and gets 0 points. Alice = 18, Bob = 12, stones = [].
The score difference is 18 - 12 = 6.
</pre>

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

<pre>
<strong>Input:</strong> stones = [7,90,5,1,100,10,10,2]
<strong>Output:</strong> 122</pre>

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

<ul>
	<li><code>n == stones.length</code></li>
	<li><code>2 &lt;= n &lt;= 1000</code></li>
	<li><code>1 &lt;= stones[i] &lt;= 1000</code></li>
</ul>

# class Solution:
#     def stoneGameVII(self, stones: List[int]) -> int:
#         n = len(stones)
#         dp = [[False for _ in range(n)] for _ in range(n)]
#         presum = [0 for _ in range(n+1)]
#         for i in range(n):
#             presum[i+1] = presum[i] + stones[i]
#         print(presum)
#         def backtrack(l, r, dp):
            
#             # stones[l: r], both inclusive
#             if l == r:
#                 return (0, 0)
#             if dp[l][r] != False:
#                 return dp[l][r]
#             # al = stones[l]+backtrack(l+1, r, dp)[1]
#             # ar = stones[r]+backtrack(l, r-1, dp)[1]
#             al = presum[r+1] - presum[l+1] + backtrack(l+1, r, dp)[1]
#             ar = presum[r] - presum[l] + backtrack(l, r-1, dp)[1]
#             bl = backtrack(l+1, r, dp)[0]
#             br = backtrack(l, r-1, dp)[0]
#             # a = max(stones[l]+backtrack(l+1, r, dp)[1], stones[r]+backtrack(l, r-1, dp)[1])
#             # b = max(backtrack(l+1, r, dp)[0], backtrack(l, r-1, dp)[0])
#             # if al > ar:
#             #     a = al
#             #     b = bl
#             #     print('a take left')
#             # elif al < ar:
#             #     a = ar
#             #     b = br
#             #     print('a take right')
#             # else:
#             #     if bl < br:
#             #         a = al
#             #         b = bl
#             #         print('a take left')
#             #     elif bl > br:
#             #         a = ar
#             #         b = br
#             #         print('a take right')
#             #     else:
#             #         a = ar
#             #         b = br
#             #         print('a take right')
#             if al - bl > ar - br:
#                 a = al
#                 b = bl
#                 print('a take left')
#             else:
#                 a = ar
#                 b = br
#                 print('a take right')
#             dp[l][r] = (a, b)
#             print(f'l={l},r={r},al={al}, bl={bl},ar={ar},br={br},diff={a-b}')
#             return (a, b)

#         a, b = backtrack(0, n-1, dp)
#         # print(dp)
#         return a-b
            
class Solution:
    def stoneGameVII(self, stones: List[int]) -> int:
        n = len(stones)
        dp = [[False for _ in range(n)] for _ in range(n)]
        presum = [0 for _ in range(n+1)]
        for i in range(n):
            presum[i+1] = presum[i] + stones[i]
        # print(presum)
        def backtrack(l, r, dp):
            
            # stones[l: r], both inclusive
            if l == r:
                return 0
            if dp[l][r] != False:
                return dp[l][r]

            al = presum[r+1] - presum[l+1]
            ar = presum[r] - presum[l]
            bl = backtrack(l+1, r, dp)
            br = backtrack(l, r-1, dp)

            if al - bl > ar - br:
                a = al
                b = bl
            else:
                a = ar
                b = br
            dp[l][r] = a-b
            # print(f'l={l},r={r},al={al}, bl={bl},ar={ar},br={br},diff={a-b}')
            return a-b

        # a, b = backtrack(0, n-1, dp)
        return backtrack(0, n-1, dp)
            

2339