Alex and Lee continue their games with piles of stones.  There are a number of piles arranged in a row, and each pile has a positive integer number of stones piles[i].  The objective of the game is to end with the most stones. 
Alex and Lee take turns, with Alex starting first.  Initially, M = 1.
On each player's turn, that player can take all the stones in the first X remaining piles, where 1 <= X <= 2M.  Then, we set M = max(M, X).
The game continues until all the stones have been taken.
Assuming Alex and Lee play optimally, return the maximum number of stones Alex can get.
 
Example 1:
Input: piles = [2,7,9,4,4]
Output: 10
Explanation:  If Alex takes one pile at the beginning, Lee takes two piles, then Alex takes 2 piles again. Alex can get 2 + 4 + 4 = 10 piles in total. If Alex takes two piles at the beginning, then Lee can take all three piles left. In this case, Alex get 2 + 7 = 9 piles in total. So we return 10 since it's larger. 

 
Constraints:

1 <= piles.length <= 100
1 <= piles[i] <= 10 ^ 4

Difficulty: interview

Starter code:

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

Solutions:
from functools import *
class Solution:
    def stoneGameII(self, arr):
        a =[]
        s=0
        n = len(arr)
        for i in arr[::-1]:
            s+=i
            a.append(s)
        a=a[::-1]
        @lru_cache(None)
        def fun(i,m):
            if i+2*m>=n:return a[i]
            mn = inf
            for ii in range(1,2*m+1):
                if ii>m:
                    ans = fun(i+ii,ii)
                else:
                    ans=fun(i+ii,m)
                if ans<mn:
                    mn = ans
            return a[i]-mn
        return fun(0,1)
                
            


from functools import lru_cache


class Solution:
    def stoneGameII(self, piles: List[int]) -> int:
        N = len(piles)
        for i in range(N - 2, -1, -1):
            piles[i] += piles[i + 1]
        
        @lru_cache(None)
        def dp(i, m):
            if i + 2 * m >= N:
                return piles[i]
            return piles[i] - min(dp(i + x, max(m, x)) for x in range(1, 2 * m + 1))
        
        return dp(0, 1)


class Solution:
    def stoneGameII(self, piles: List[int]) -> int:
        
        for i in range(len(piles)-2, -1, -1):
            piles[i] += piles[i+1]
        
        memo = {}
        def dfs(i, m):
            if i + (2 * m) >= len(piles):
                return piles[i]
            if (i, m) in memo:
                return memo[(i, m)]
            
            memo[(i, m)] = piles[i] - min((dfs(i+j, max(m, j))) for j in range(1, (2*m)+1))
            return memo[(i, m)]
        
        
        return dfs(0, 1)

class Solution:
    def stoneGameII(self, piles: List[int]) -> int:
        N = len(piles)
        suffix_sum = [0] * N
        
        running_sum = 0
        for idx in range(N-1, -1, -1):
            running_sum += piles[idx]
            suffix_sum[idx] = running_sum
            
        DP = [[0]*(N) for _ in range(N)]
        
        for pile_no in reversed(list(range(N))):
            for M in reversed(list(range(N))):
                min_next_player = suffix_sum[pile_no]
                for x in range(1, 2*M + 1):
                    if pile_no + x < N:
                        min_next_player = min(min_next_player, DP[pile_no + x][max(x,M)])
                    else:
                        min_next_player = 0
                DP[pile_no][M] = suffix_sum[pile_no] - min_next_player
            
        return DP[0][1]
        
#         # @lru_cache(None)
#         def dfs(pile_no, M):
#             if pile_no > N-1:
#                 return 0
#             if DP[pile_no][M] > 0:
#                 return DP[pile_no][M]
#             min_next_player = suffix_sum[pile_no]
#             for x in range(1, min(2*M + 1, N+1)):
#                 min_next_player = min(min_next_player, dfs(pile_no + x, max(x,M)))
                
#             DP[pile_no][M] = suffix_sum[pile_no] - min_next_player
#             return DP[pile_no][M]
            
#         return dfs(0, 1)
        
            
        
        
        
        
            


\"\"\"
dp[i][j] = the max score one can get with [i:] piles and M = j.
dp[i][j] = max(sum(piles[i:i+x]) - dp[i+x][max(j, x)] for x in range(1, min(2*j, n))
dp[i][n] = sum(piles[i:])
\"\"\"
class Solution:
    def stoneGameII(self, piles: List[int]) -> int:
        n = len(piles)
        suf_sum = [0 for _ in range(n + 1)]     # 先构造一个suffix sum
        for i in range(n - 1, -1, -1):
            suf_sum[i] = suf_sum[i+1] + piles[i]
            
        dp = [[0 for _ in range(n + 1)] for _ in range(n + 1)]
        # for i in range(n + 1):
        #     dp[i][n] = suf_sum[i]
        
        for i in range(n, -1, -1):
            for j in range(n, 0, -1):
                for x in range(1, min(2*j, n - i) + 1):
                    dp[i][j] = max(dp[i][j], suf_sum[i] - dp[i+x][max(j, x)])
        return dp[0][1]

class Solution:
    def stoneGameII(self, piles: List[int]) -> int:
        N = len(piles)
        self.dp = {}

        def recursiveStoneGame(start, M):            
            if start >= N:
                return 0
            
            # take all if possible
            if N - start <= 2*M:
                return sum(piles[start:])
            
\t\t\t# memoization
            if (start, M) in self.dp:
                return self.dp[(start, M)]

            alex_score = 0
            sum_score = sum(piles[start:])  # all available score
\t\t\t
\t\t\t# explore each x
            for x in range(1, 2*M+1):
\t\t\t    # get opponent's score
                opponent_score = recursiveStoneGame(start+x, max(x, M))
\t\t\t\t# diff is the current palyers score, keep max
                alex_score = max(alex_score, sum_score - opponent_score)
                
            self.dp[(start, M)] = alex_score
                
            return alex_score
        
        
        return recursiveStoneGame(0, 1)

class Solution:
    def stoneGameII(self, piles: List[int]) -> int:
        
        for i in range(len(piles)-2, -1, -1):
            piles[i] += piles[i+1]
            
        from functools import lru_cache
        @lru_cache(None)
        def dp(index, m):
            if index >= len(piles):
                return 0
            max_val = 0
            
            for i in range(index, min(index+2*m, len(piles))):
                new_m = max(m, i+1-index)
                max_val = max(max_val, piles[index] - dp(i+1, new_m))
            return max_val
        return dp(0, 1)
            
#         N = len(piles)
#         for i in range(N-2, -1, -1):
#             piles[i] += piles[i+1]
#         print(piles)
#         from functools import lru_cache
#         @lru_cache(None)
#         def dp(i, m):
#             if i + 2 * m >= N: return piles[i]
#             return piles[i] - min(dp(i + x, max(m, x)) for x in range(1, 2 * m + 1))
#         return dp(0, 1)
        max_num = 0
        def play(i, m, player):
         
            
            if i >= len(piles):
                return 0
            
            if player == 1:
                point = play(i+2*m, 2*m, 0)
              
                return point
            else:
                
                max_point = 0
                for action in range(i+1, min(i+1+2 *m, len(piles))):
                    print((sum(piles[i:action]), i, m, action, piles[i:action], min(i+1+2 *m, len(piles))))
                    down_stream_point = play(action, max(action, m), 1)
                    max_point = max(max_point, sum(piles[i:action]) + down_stream_point)
                  
                return max_point
            
        return play(0, 1, 0)


class Solution:
    def stoneGameII(self, piles: List[int]) -> int:
        N = len(piles)
        cache = {}
        
        def recursive_game(start, M):
            score_left = sum(piles[start:])
            if start >= N: return 0
            if (start, M) in cache: return cache[(start,M)]
            if start + 2*M >= N: return score_left
            
            my_score = 0
            for x in range(1,2*M+1):
                opponent_score = recursive_game(start + x, max(M,x))
                my_score = max(my_score, score_left-opponent_score)
                
            cache[(start,M)] = my_score
            return my_score
        
        return recursive_game(0,1)

class Solution:
    def stoneGameII(self, piles: List[int]) -> int:
        from functools import lru_cache
        
        @lru_cache(None)
        def select(start, M, my_turn):
            if my_turn:
                if start + 2*M >= len(piles):
                    return sum(piles[start:])
                rst = 0
                for i in range(1, 2*M+1):
                    rst = max(rst, sum(piles[start:start+i]) + select(start+i, max(i, M), False))
                return rst
            
            if start + 2*M >= len(piles):
                return 0
            rst = float('inf')
            for i in range(1, 2*M+1):
                rst = min(rst, select(start+i, max(i, M), True))
            return rst
        
        return select(0, 1, True)
        
        
        
                       


class Solution:
    def stoneGameII(self, A: List[int]) -> int:
        
        
        
        # my solution ... 
        #  time: O()
        # space: O()
        
        seen = {}
        def max_stones(sidx, m):  # 返回面对 A[sidx:] 时，直至游戏结束，所能取到的最多石头
            if sidx == len(A):
                return 0
            if (sidx, m) not in seen:
                if len(A)-sidx <= 2*m:
                    seen[sidx, m] = sum(A[sidx:])
                else:
                    res = 0
                    for x in range(1, 2*m+1):
                        new_sidx = sidx + x
                        res = max(res, sum(A[sidx:]) - max_stones(new_sidx, max(m, x)))
                    seen[sidx, m] = res
            return seen[sidx, m]
        
        return max_stones(0, 1)
        
        


class Solution:
    def stoneGameII(self, piles: List[int]) -> int:  
        # store (start, M)
        table = {}
        
        def stoneGameRec(start, M):
            if (start, M) in table:
                return table[(start, M)]            
            
            totalTaken = 0
            for i in range(start, min(start + 2 * M, len(piles))):
                totalTaken += piles[i]
                           
            if start + 2 * M >= len(piles):
               return (totalTaken, 0)

            maxStones = (0, 0)
            for i in range(start + 2 * M - 1, start - 1, -1):                    
                X = i - start + 1                            
                theirStones, yourStones = stoneGameRec(i + 1, max(M, X))
                yourStones += totalTaken
                if yourStones > maxStones[0]:
                    maxStones = (yourStones, theirStones)

                totalTaken -= piles[i]

            table[(start, M)] = maxStones
            return maxStones                                                 
                
        alexScore, _ = stoneGameRec(0, 1)                                
        return alexScore


class Solution:
    def stoneGameII(self, piles: List[int]) -> int:
        memo = {}
        prefix = [0] * (len(piles) + 1)
        for i in range(len(piles)):
            prefix[i+1] += prefix[i] + piles[i]
        return self.dfs(piles, memo, 0, 1, prefix)
    
    
    def dfs(self, piles, memo, i, m, prefix):
        if i == len(piles):
            return 0

        if (i, m) in memo:
            return memo[(i, m)]
        
        ans = float('-inf')
        for j in range(1, m+1):
            if i + j <= len(piles):
                ans = max(ans, prefix[-1] - prefix[i] - self.dfs(piles, memo, i+j, m, prefix))
            
        for j in range(m+1, 2 * m + 1):
            if i + j <= len(piles):
                ans = max(ans, prefix[-1] - prefix[i] - self.dfs(piles, memo, i+j, j, prefix))
                
        memo[(i, m)] = ans
        
        return memo[(i, m)]
            
            


class Solution:
    def stoneGameII(self, piles: List[int]) -> int:
        n = len(piles)
        # dp[i][M] means the number of stones one can get starting with i with M
        dp = [[0 for m in range(n)] for i in range(n)]
        sufsum = [0] * (n + 1)
        for i in reversed(range(n)):
            sufsum[i] = sufsum[i + 1] + piles[i]
        
        return self.dfs(piles, 0, dp, sufsum, 1)
    
    def dfs(self, piles, index, dp, sufsum, M):
        if index == len(piles):
            return 0
        
        if dp[index][M] > 0:
            return dp[index][M]
        
        result = 0
        for i in range(index, index + 2 * M):
            if i >= len(piles):
                break

            X = i - index + 1
            result = max(result, sufsum[index] - self.dfs(piles, i + 1, dp, sufsum, max(X, M)))
        
        dp[index][M] = result
        return dp[index][M]

class Solution:
    def stoneGameII(self, piles: List[int]) -> int:
        n = len(piles)
        # dp[i][M] means the number of stones one can get starting with i with M
        dp = [[0 for m in range(n)] for i in range(n)]
        sufsum = [0] * (n + 1)
        for i in reversed(range(n)):
            sufsum[i] = sufsum[i + 1] + piles[i]
        
        return self.dfs(piles, 0, dp, sufsum, 1)
    
    def dfs(self, piles, index, dp, sufsum, M):
        if index == len(piles):
            return 0
        
        if dp[index][M] > 0:
            return dp[index][M]
        
        s = 0
        result = 0
        for i in range(index, index + 2 * M):
            if i >= len(piles):
                break

            s += piles[i]
            X = i - index + 1
            result = max(result, s + sufsum[i + 1] - self.dfs(piles, i + 1, dp, sufsum, max(X, M)))
        
        dp[index][M] = result
        return dp[index][M]

import functools
class Solution:
    def stoneGameII(self, piles: List[int]) -> int:
        n = len(piles)
        for i in range(n-2, -1, -1):
            piles[i] += piles[i+1] # suffix sum
        
        # 在位置i，M=m的情况下，当前选手获得的最大分数
        @lru_cache(None)
        def dp(i, m):
            if i+2*m >= n: return piles[i]
            #                      在当前player选择x下，对手能得到的最大分数
            # 选择了x，就是给对方设置了M
            # return piles[i] - min([dp(i+x, max(m,x)) for x in range(1, 2*m+1)])
            # 写成这样更清晰
            res = 0
            for x in range(1, 2*m+1):
                res = max(res, piles[i] - dp(i+x, max(m,x)))
            return res
        return dp(0, 1)

class Solution:
    def stoneGameII(self, piles: List[int]) -> int:
        m = len(piles)
        dp = [[0 for j in range(m+1)] for i in range(m)]
        sumv = 0
        for i in range(m-1, -1, -1):
            sumv += piles[i]
            for M in range(1, len(dp[0])):
                if 2 * M + i >= m:
                    dp[i][M] = sumv
                else:
                    for x in range(1, 2*M+1):
                        dp[i][M] = max(dp[i][M], sumv - dp[i+x][max(M, x)])
        return dp[0][1]

class Solution:
    def stoneGameII(self, piles: List[int]) -> int:
        
        mem = {}
        
        def dp(i, M):
            if (i,M) in mem:
                return mem[(i,M)][0]
            if i >= len(piles):
                return 0
            
            val = []
            for x in range(1, min(2*M, len(piles)-i)+1):
                val.append(sum(piles[i:i+x]) - dp(i+x, max(x, M)))
            
            mem[(i,M)] = [max(val), val.index(max(val))]
            return mem[(i,M)][0]
                        
        dp(0,1)
        
        i, m, s, t = 0, 1, 0, 1
        while i<len(piles):
            x = mem[(i, m)][1]+1
            if t == 1:
                s += sum(piles[i:i+x])
            t *= -1
            i = i+x
            m = max(x, m)
        
        return s


class Solution:
  def stoneGameII(self, piles: List[int]) -> int:
    n = len(piles)
    dp = [[-1 for _ in range(n+1)] for _ in range(n+1)]
    s = sum(piles)
    def helper(st, M):
      nonlocal n, piles, dp
      if st >= n:
        return 0
      if dp[M][st] != -1:
        return dp[M][st]
      cur = 0
      tmp = float('-inf')
      for x in range(1, 2*M+1):
        if st + x > n:
          continue
        
        tmp = max(tmp, sum(piles[st: st+x]) - helper(st+x, max(M, x)))
                  
      dp[M][st] = tmp 
      return tmp
    return int((helper(0,1) + s)/2)
      


class Solution:
    def stoneGameII(self, piles: List[int]) -> int:
      N = len(piles)
      @lru_cache(maxsize=None)
      def recurse(idx, m, alexTurn):
        # print(f\"RECURSE {idx} {m} {alexTurn}\")
        if idx + 2*m > N-1:

          return (sum(piles[idx:]), 0) if alexTurn else (0, sum(piles[idx:]))
          # return (0, 0)
        ops = []
        for x in range(1, 2*m+1):
          curNumStones = sum(piles[idx:idx+x])
          (nextA, nextL) = recurse(idx+x, max(m, x), not alexTurn)
          if alexTurn:
            ops.append((nextA+curNumStones, nextL))
          else:
            ops.append((nextA, nextL+curNumStones))
        [aScores, lScores] = list(zip(*ops)) 
        if alexTurn:
          return (max(aScores), max(lScores))
        else:
          return (min(aScores), max(lScores))
      return recurse(0, 1, True)[0]
    
    \"\"\"
    recurse(0, 1, True) -> 
      2 + recurse(1, 1, False) 
        recurse(1, 1, False) -> 
          9 + recurse(2, 1, True) 
          9 + 4 + recurse(3, 2, True)
      9 + recurse(2, 2, False)
          
    \"\"\"

class Solution:
    def stoneGameII(self, piles: List[int]) -> int:
        n = len(piles)
        s = sum(piles[:])
        memo = [[-sys.maxsize for i in range(2*n)] for j in range(n)]
        
        def DFS(m:int,index:int)->int:
            if memo[m][index]!=-sys.maxsize:
                return memo[m][index]
            if index>=n:
                return 0
            score = -sys.maxsize
            take = min(n-1,index+2*m-1)
            
            for i in range(index,take+1):
                score = max(score,sum(piles[index:i+1])-DFS(max(i-index+1,m),i+1))
                #print(index,i+1,sum(piles[index:i+1]),score)
            memo[m][index]=score
            return score
                            
                            
        return (DFS(1,0)+s)//2

class Solution:
    def stoneGameII(self, piles: List[int]) -> int:
        n = len(piles)
        post = [0] * (n+1)
        for i in range(n-1, -1, -1):
            post[i] = post[i+1] + piles[i]
        
        dp = [[-1]*200 for _ in range(101)]
        
        def solve(i, m):
            if i >= len(piles):
                return 0
            if dp[i][m] > 0:
                return dp[i][m]
            s = ans = 0
            for di in range(1, 2*m+1):
                ii = i + di - 1
                if ii >= len(piles):
                    break
                s += piles[ii]
                other = solve(ii+1, max(m, di))
                ans = max(ans, s + post[ii+1] - other)
            dp[i][m] = ans
            return ans
        return solve(0, 1)


class Solution:
    def stoneGameII(self, piles: List[int]) -> int:
        n = len(piles)
        @lru_cache(None)
        def dp(i, m):
            if i == n:
                return 0, 0
            s = 0
            a, b = 0, 10 ** 8
            for j in range(min(2 * m, n - i)):
                s += piles[i + j]
                c, d = dp(i + j + 1, max(j + 1, m))
                a = max(a, s + d)
                b = min(b, c)
            return a, b
        return dp(0, 1)[0]


class Solution:
    
    def stoneGameII(self, piles: List[int]) -> int:
        def dfs(piles, l, m):
            if (l, m) in self.mem:
                return self.mem[(l, m)]
            ret = 0
            r = min(len(piles), l+2*m)
            for i in range(l+1, r+1):
                other = dfs(piles, i, max(m, i-l))
                cur = sum(piles[l:]) - other
                ret = max(ret, cur)
            self.mem[(l, m)] = ret
            return ret
        
        self.mem = dict()
        return dfs(piles, 0, 1)
    
    '''
    def stoneGameII(self, piles: List[int]) -> int:
        def dfs(piles, m):
            ret = 0
            r = min(len(piles), 2*m)
            for i in range(1, r+1):
                other = dfs(piles[i:], max(m, i))
                cur = sum(piles) - other
                ret = max(ret, cur)
            return ret
        
        ans = dfs(piles, 1)
        return ans
    '''

class Solution:
    def stoneGameII(self, piles: List[int]) -> int:
        dp = dict()
        def dfs(i, m):
            if m >= len(piles) - i:
                return sum(piles[i:])
            elif (i, m) in dp:
                return dp[(i, m)]
            else:
                dp[(i, m)] = max([(sum(piles[i:]) - dfs(i+idx+1, max(m, idx+1))) for idx in range(2*m)])
                return dp[(i, m)]
        
        return dfs(0, 1)

class Solution:
    def stoneGameII(self, piles: List[int]) -> int:
        n = len(piles)
        
        @lru_cache(None)
        def dp1(prev, m):
            
            if prev >= n-1:
                return 0
            
            maxcount = 0
            
            for x in range(1, m*2+1):
                if prev+x >= n:
                    break
                    
                ret = dp2(prev+x, max(m, x)) 
                maxcount = max(maxcount, ret+ sum(piles[prev+1:prev+x+1]))
                #print(prev+x, m, x, ret, sum(piles[prev+1:prev+x+1]))
            return maxcount

        @lru_cache(None)
        def dp2(prev, m):
            
            if prev >= n-1:
                return 0
            
            maxcount = float('inf')
            
            for x in range(1, m*2+1):
                if prev+x >= n:
                    break
                ret = dp1(prev+x, max(m, x)) 
                maxcount = min(maxcount, ret)
            
            return maxcount
        return dp1(-1, 1)
                


class Solution:
    def stoneGameII(self, piles: List[int]) -> int:
        A, n = piles, len(piles)
        for i in range(n-2, -1, -1):
            A[i] += A[i+1]
        @lru_cache(maxsize=None)
        def helper(i, m):
            # return the max points current player can get from piles[i:]
            if i + 2*m >= len(piles):
                return A[i]
            res = 0            
            for x in range(1, 2*m+1):
                res = max(res, A[i] - helper(i+x, max(m, x)))
            return res
        
        return helper(0, 1)

import math
from functools import lru_cache

class Solution:
    def stoneGameII(self, piles: List[int]) -> int:
        solved = {}
        ps = [0] + piles[:]
        for i in range(1, len(ps)):
            ps[i] += ps[i - 1]
        
        @lru_cache(None)
        def solve(p, m, is_alex):
            # if (p, m, is_alex) in solved:
                # return solved[(p, m, is_alex)]
            if p >= len(piles):
                return 0
            if is_alex:
                ms = -math.inf
                for x in range(1, 2 * m + 1):
                    if p + x < len(ps):
                        ms = max(ms, ps[p + x] - ps[p] + solve(p + x, max(x, m), not is_alex))
                    else:
                        break
            else:
                ms = math.inf
                for x in range(1, 2 * m + 1):
                    if p + x < len(ps):
                        ms = min(ms, - (ps[p + x] - ps[p]) + solve(p + x, max(x, m), not is_alex))
                    else:
                        break
            solved[(p, m, is_alex)] = ms
            return solved[(p, m, is_alex)]
        
        diff = solve(0, 1, True)
        return (ps[-1] + diff) // 2

class Solution:
    def stoneGameII(self, piles: List[int]) -> int:
        l = len(piles)
        self.len = l
        dp = {}
        
        total = sum(piles)
        
        maxDiff = self.help(piles, 0, 1, dp)
    
        return int((total+ maxDiff)/2)
    
    def help(self, piles, index, m, dp):
        
        if index >= self.len:
            return 0
        
        if dp.get((index, m)) != None:
            return dp.get((index,m))
        
        res = -0xFFFFFFF
        s = 0
        for i in range(index, self.len):
            if i - 2*m >= index:
                break
            s += piles[i]
            res = max(res, s - self.help(piles, i+1, max(m, i - index + 1), dp))
        
        dp[(index, m)] = res
        
        return res

class Solution:
    def stoneGameII(self, piles: List[int]) -> int:
        def Util(alexTurn, index, m) -> int:
            \"\"\"
            Returns the Maximum sum of Alex
            \"\"\"
            if (index >= len(self.piles)):
                return 0
            if (index == len(self.piles) - 1):
                return self.piles[index]
            # print(f\"alexTurn = {alexTurn} index = {index} m = {m}\")
            if (self.dp[index][m] != -1):
                return self.dp[index][m]
            
            totalCounts = 0
            ans = 0

            for x in range(2*m):
                if (index + x == len(self.piles)):
                    break
                totalCounts += self.piles[index + x]
                if (index + x + 1 <= len(self.piles)):
                    nextSum = Util(not alexTurn, index + x + 1, max(m, x+1))
                    # print(index + x + 1)
                    if (index + x + 1 == len(self.piles)):
                        ans = max(ans, totalCounts)
                    else:
                        ans = max(ans, totalCounts + self.presum[index + x + 1] - nextSum)
                    # print(f\"index = {index + x + 1} m = {m} nextSum = {nextSum}\")

            self.dp[index][m] = ans
            # print(f\"index = {index} m = {m} ans = {ans} totalCounts = {totalCounts}\")

            return ans
        
        self.presum = copy.copy(piles)
        for i in reversed(range(len(piles) - 1)):
            self.presum[i] += self.presum[i + 1]
        # print(self.presum)
        self.dp = [-1]*len(piles)
        for j in range(len(piles)):
            self.dp[j] = [-1] * len(piles)
                
        self.piles = piles
        return Util(True, 0, 1)
        

import numpy as np
from functools import lru_cache
class Solution:
    def stoneGameII(self, piles: List[int]) -> int:
        cumsum=np.cumsum(piles[::-1])
        @lru_cache(None)
        def optimalValue(m,s):
            if s==0: return 0
            cumsum[s-1]
            return max([cumsum[s-1]-optimalValue(max(m,n),s-n) for n in range(1,2*m+1) if s-n>=0])
        return optimalValue(1,len(piles))


from functools import lru_cache
class Solution:
    def stoneGameII(self, a: List[int]) -> int:
        n = len(a)
        sums = [0] * n
        sums[-1] = a[-1]
        for i in reversed(range(len(sums)- 1)):
            sums[i] = a[i] + sums[i+1]
            
        @lru_cache(None)
        def dp(i, m):
            if i >= n: return 0
            return max(sums[i] - dp(i + x, max(x,m)) for x in range(1, 2*m + 1))
        
        return dp(0, 1)

MIN = float('-inf')
class Solution:
    def stoneGameII(self, piles):
        
        n = len(piles)
        preSum = [0] * (n+1)
        for i in range(1,n+1):
            preSum[i] += preSum[i-1] + piles[i-1]
        
        def dfs(start, M, memo):
            if start == n:
                return 0
            if (start,M) in memo:
                return memo[(start,M)]
            max_diff = MIN
            for X in range(1, 2*M+1):
                end = min(n, start+X)
                cur = preSum[end] - preSum[start]
                max_diff = max(max_diff, cur-dfs(end, max(M,X), memo))
            memo[(start,M)] = max_diff
            return max_diff
        
        total = sum(piles)
        return (dfs(0, 1, {})+total) // 2
        


import math

class Solution:
    def stoneGameII(self, piles: List[int]) -> int:
        solved = {}
        ps = [0] + piles[:]
        for i in range(1, len(ps)):
            ps[i] += ps[i - 1]
        
        def solve(p, m, is_alex):
            if (p, m, is_alex) in solved:
                return solved[(p, m, is_alex)]
            if p >= len(piles):
                return 0
            if is_alex:
                ms = -math.inf
                for x in range(1, 2 * m + 1):
                    if p + x < len(ps):
                        ms = max(ms, ps[p + x] - ps[p] + solve(p + x, max(x, m), not is_alex))
                    else:
                        break
            else:
                ms = math.inf
                for x in range(1, 2 * m + 1):
                    if p + x < len(ps):
                        ms = min(ms, - (ps[p + x] - ps[p]) + solve(p + x, max(x, m), not is_alex))
                    else:
                        break
            solved[(p, m, is_alex)] = ms
            return solved[(p, m, is_alex)]
        
        diff = solve(0, 1, True)
        return (sum(piles) + diff) // 2

from functools import lru_cache

class Solution:
    def stoneGameII(self, piles: List[int]) -> int:
        n = len(piles)
        
        @lru_cache(None)
        def value(M, ind):
            if ind >= n:
                return 0
            
            v_max = 0
            for X in range(1, 2*M + 1):
                M_new = max(X, M)
                v = sum(piles[ind:]) - value(M_new, ind+X)
                v_max = max(v, v_max)
            return v_max
        
        val = value(1, 0)
        return val

from functools import lru_cache
class Solution:
    def stoneGameII(self, piles: List[int]) -> int:
        # dp[i,m] = max stones the current player can take from piles[i:] with M = m
        # which means 1 <= x <= 2M
        # use backwards prefix sum A[i] = totel stones of piles[i:]
        # means how many more the current player can take for max
        # the other player stones dp[i+x, max(m,x)]
        # the current player stone = A[i] - dp[i+x, max(m,x)]
        
        N = len(piles)
        for i in range(N-2, -1, -1):
          piles[i] += piles[i+1]
        
        @lru_cache(None)
        def dp(i, m):
          if i + 2*m >= N:
            return piles[i] # take as many as possible
          min_left = float('inf')
          for x in range(1, 2*m+1):
            min_left = min(min_left, dp(i+x, max(m, x)))
          return piles[i] - min_left
        
        return dp(0,1)

class Solution:
    def rec(self, i, m, t):
            if self.memo[i][m][t]!=-1:
                return self.memo[i][m][t]
            
            if i==self.n:
                return 0
            
            if t==0:
                res, now = 0, 0
                
                for j in range(2*m):
                    if i+j>=self.n:
                        break
                    now += self.piles[i+j]
                    res = max(res, now+self.rec(i+j+1, max(m, j+1), 1))
            else:
                res = 10**18
                
                for j in range(2*m):
                    if i+j>=self.n:
                        break
                    res = min(res, self.rec(i+j+1, max(m, j+1), 0))
            
            self.memo[i][m][t] = res
            return res

    def stoneGameII(self, piles: List[int]) -> int:
        self.n = len(piles)
        self.piles = piles
        self.memo = [[[-1]*2 for _ in range(110)] for _ in range(self.n+1)]
        return self.rec(0, 1, 0)

import math

class Solution:
    def stoneGameII(self, piles: List[int]) -> int:
        solved = {}
        ps = [0] + piles[:]
        for i in range(1, len(ps)):
            ps[i] += ps[i - 1]
        
        def solve(p, m, is_alex):
            if (p, m, is_alex) in solved:
                return solved[(p, m, is_alex)]
            if p >= len(piles):
                return 0
            if is_alex:
                ms = -math.inf
                for x in range(1, 2 * m + 1):
                    if p + x < len(ps):
                        ms = max(ms, ps[p + x] - ps[p] + solve(p + x, max(x, m), not is_alex))
            else:
                ms = math.inf
                for x in range(1, 2 * m + 1):
                    if p + x < len(ps):
                        ms = min(ms, - (ps[p + x] - ps[p]) + solve(p + x, max(x, m), not is_alex))
            solved[(p, m, is_alex)] = ms
            return solved[(p, m, is_alex)]
        
        diff = solve(0, 1, True)
        return (sum(piles) + diff) // 2

class Solution:
    def stoneGameII(self, piles: List[int]) -> int:
        def Util(alexTurn, index, m) -> int:
            \"\"\"
            Returns the Maximum sum of Alex
            \"\"\"
            if (index >= len(self.piles)):
                return 0
            turn = 1 if alexTurn is True else 0

            # print(f\"alexTurn = {alexTurn} index = {index} m = {m}\")
            if (self.dp[turn][index][m] != -1):
                return self.dp[turn][index][m]
            
            totalCounts = 0
            ans = 0
            if (alexTurn):
                ans = 0
                for x in range(2*m):
                    if (index + x == len(self.piles)):
                        break
                    totalCounts += self.piles[index + x]
                    alexSum = Util(not alexTurn, index + x + 1, max(m, x+1))
                    # print(f\"alexSum = {alexSum} index = {index} x = {x} M = {max(m, x + 1)} ans = {alexSum + totalCounts}\")
                    ans = max(alexSum + totalCounts, ans)
                # print(f\"alexTurn = {alexTurn} index = {index} x = {x} M = {max(m, x + 1)} ans = {alexSum + totalCounts}\")

            else:
                ans = sys.maxsize
                for x in range(2*m):
                    if (index + x == len(self.piles)):
                        break
                    totalCounts += self.piles[index + x]
                    alexSum = Util(not alexTurn, index + x + 1, max(m, x+1))
                    ans = min(alexSum, ans)
                # print(f\"alexTurn = {alexTurn} index = {index} x = {x} M = {max(m, x + 1)} ans = {alexSum + totalCounts}\")
            self.dp[turn][index][m] = ans
            return ans
        self.dp = [-1]*2
        for i in range(2):
            self.dp[i] = [-1]*len(piles)
            for j in range(len(piles)):
                self.dp[i][j] = [-1] * len(piles)
                
        self.piles = piles
        return Util(True, 0, 1)
        

\"\"\"
There are 2 pieces of information to memo: 1. Alice's maximum score, 2. Bob's maximum score. Combine them into a tuple and store it in a dict, the key of which is (current index, m).
We will start from the piles[index], and compute the cumulative sum all the way up to piles[index+2*m].
Then we recursively call the DP function with the new index and m. After trying all the possible ways, take the maximum value, and store it in the dict.

\"\"\"
class Solution:
    def stoneGameII(self, piles):
        d = {} # (idx, m): (Alice's score, Bob's score)
        def DP(idx, m):
            if idx>=len(piles):
                return (0,0)
            if (idx,m) in d:
                return d[(idx,m)] # Memo!
            s, ans, oppo = 0, 0, 0
            for i in range(idx, idx+2*m): # try all the possible sum
                if i>=len(piles):
                    break
                s += piles[i]
                dp_ans = DP(i+1, max(m, i-idx+1)) # fetch the result from subproblem
                if s+dp_ans[1]>ans:
                    ans = s+dp_ans[1] # [1] is the real Alice's score from the next subproblem
                    oppo = dp_ans[0] # [0] is Bob's score
            d[(idx,m)] = (ans, oppo) # store the information
            return (ans, oppo)

        ans = DP(0, 1)
        return ans[0]

class Solution:
    def stoneGameII(self, piles: List[int]) -> int:
        def Util(alexTurn, index, m) -> int:
            \"\"\"
            Returns the Maximum sum of Alex
            \"\"\"
            if (index >= len(self.piles)):
                return 0
            turn = 1 if alexTurn is True else 0

            # print(f\"alexTurn = {alexTurn} index = {index} m = {m}\")
            if (self.dp[turn][index][m] != -1):
                return self.dp[turn][index][m]
            
            totalCounts = 0
            ans = 0
            if (alexTurn):
                ans = -sys.maxsize
            else:
                ans = sys.maxsize
            for x in range(2*m):
                if (index + x == len(self.piles)):
                    break
                totalCounts += self.piles[index + x]
                alexSum = Util(not alexTurn, index + x + 1, max(m, x+1))
                # print(f\"alexSum = {alexSum} index = {index} x = {x} M = {max(m, x + 1)} ans = {alexSum + totalCounts}\")
                if (alexTurn):
                    ans = max(alexSum + totalCounts, ans)
                else:
                    ans = min(alexSum, ans)
            # print(f\"alexTurn = {alexTurn} index = {index} x = {x} M = {max(m, x + 1)} ans = {alexSum + totalCounts}\")

#             else:
#                 ans = sys.maxsize
#                 for x in range(2*m):
#                     if (index + x == len(self.piles)):
#                         break
#                     totalCounts += self.piles[index + x]
#                     alexSum = Util(not alexTurn, index + x + 1, max(m, x+1))
#                     ans = min(alexSum, ans)
                # print(f\"alexTurn = {alexTurn} index = {index} x = {x} M = {max(m, x + 1)} ans = {alexSum + totalCounts}\")
            self.dp[turn][index][m] = ans
            return ans
        self.dp = [-1]*2
        for i in range(2):
            self.dp[i] = [-1]*len(piles)
            for j in range(len(piles)):
                self.dp[i][j] = [-1] * len(piles)
                
        self.piles = piles
        return Util(True, 0, 1)
        

class Solution:
    def stoneGameII(self, piles: List[int]) -> int:
        n = len(piles)
        prefix_sum = [0] * (n+1)
        for i in range(1, len(prefix_sum)):
            prefix_sum[i] = prefix_sum[i-1] + piles[i-1]
        memo = {}
        def dfs(pos, m, player1):
            if pos >= len(piles):
                return 0
            if (pos, m, int(player1)) in memo:
                return memo[(pos, m, int(player1))]
            
            if player1:
                best_score = -sys.maxsize
            else:
                best_score = sys.maxsize
                    
            for x in range(1, 2*m + 1):
                if pos + x > len(piles):
                    break
                score = dfs(pos + x, max(m, x), not player1)
                if player1:
                    score += prefix_sum[pos+x] - prefix_sum[pos]
                    best_score = max(best_score, score)
                else:
                    best_score = min(best_score, score)
            memo[(pos,m,int(player1))] = best_score
            return best_score
        return dfs(0, 1, True)

class Solution:
    def helper(self, s, M, n):
        if s >= n:
            return 0
        if (s, M) in self.mem:
            return self.mem[(s, M)]
        cur, best = 0, -float('inf')
        for x in range(1, 2*M + 1):
            if s + x > n:
                break
            cur += self.piles[s + x -1]
            best = max(best, cur - self.helper(s + x, max(x, M), n))
        self.mem[(s, M)] = best
        return best
                
        
    def stoneGameII(self, piles: List[int]) -> int:
        n = len(piles)
        self.mem = {}
        self.piles = piles
        return (sum(piles) + self.helper(0, 1, n))//2


class Solution:
    def stoneGameII(self, piles: List[int]) -> int:
        @lru_cache(None)
        def minimax(start, m, player):
            if start >= len(piles):
                return 0
            if player == 1:
                #Alex's turn
                return max(sum(piles[start:start + x]) + minimax(start + x ,max(x, m),2) for x in range(1, 2*m + 1))
            if player == 2:
                return min(minimax(start + x, max(x, m), 1) for x in range(1, 2*m + 1))
        # @lru_cache
        # def getsum(start, end, input):
        return minimax(0, 1, 1)
        
                
                
                
                
                
                
#         result = dict()
#         result_min = dict()
        
#         def minimax(start, M, player):
#             if start >= len(piles):
#                 return 0
#             if player == 1:
#                 # maxnum = -1
#                 if (start, M) in result:
#                     return result[(start, M)]
#                 maxnum = -1
#                 for X in range(1, 2 * M + 1):
#                     temp = minimax(start + X, max(X, M), 2) + sum(piles[start:start + X])
#                     if temp > maxnum:
#                         maxnum = temp
#                 result[(start, M)] = maxnum
#                 return maxnum
                
#             if player == 2:
#                 #minimize
#                 minnum = 10^5
#                 if (start, M) in result_min:
#                     return result_min[(start, M)]
#                 minnum = 1000000
#                 for X in range(1, 2 * M + 1):
#                     temp = minimax(start + X, max(X, M), 1)
#                     if temp < minnum:
#                         minnum = temp
#                 result_min[(start, M)] = minnum
#                 return minnum
#         res = minimax(0, 1, 1)
#         print(result)
#         print(result_min)
#         return res


class Solution:
    def stoneGameII(self, piles: List[int]) -> int:
        n = len(piles)
        prefix_sum = [0] * (n+1)
        for i in range(1, len(prefix_sum)):
            prefix_sum[i] = prefix_sum[i-1] + piles[i-1]
        memo = {}
        def dfs(pos, m, player1):
            if pos >= len(piles):
                return (0, 0)
            if (pos, m, int(player1)) in memo:
                return memo[(pos, m, int(player1))]
            
            if player1:
                best_score = -sys.maxsize
                p1_score = 0
            else:
                best_score = sys.maxsize
                p1_score = 0
                    
            for x in range(1, 2*m + 1):
                if pos + x > len(piles):
                    break
                score, p1_score_candidate = dfs(pos + x, max(m, x), not player1)
                if player1:
                    score += prefix_sum[pos+x] - prefix_sum[pos]
                    if score > best_score:
                        p1_score = p1_score_candidate + prefix_sum[pos+x] - prefix_sum[pos]
                        best_score = score
                else:
                    score += -prefix_sum[pos+x] + prefix_sum[pos]
                    if score < best_score:
                        best_score = score
                        p1_score = p1_score_candidate
            memo[(pos,m,int(player1))] = (best_score, p1_score)
            return (best_score, p1_score)
        return dfs(0, 1, True)[1]

class Solution:
    def stoneGameII(self, piles: List[int]) -> int:
        length = len(piles)
        dp = [[0]*length for i in range(length)]
        visited = [[0]*(length+1) for i in range(length+1)]
        
        def helper(index,M):
            if index==length:
                return 0
            if visited[index][M]!=0:
                return dp[index][M]
            best = float('-inf')
            for i in range(1,2*M+1):
                astones = sum(piles[index:index+i])
                score = astones-helper(min(index+i,length),min(max(M,i),length))
                best = max(score,best)
            dp[index][M] = best
            visited[index][M] = 1
            return best
        total = sum(piles)
        diff = helper(0,1)
        return (total+diff)//2

class Solution:
    def stoneGameII(self, piles: List[int]) -> int:
        for i in range(len(piles) -2, -1, -1):
            piles[i] += + piles[i + 1]
        
        from functools import lru_cache
        @lru_cache(None)
        def takeStone(startInd, M):
            #print(startInd, M)
            if startInd + 2*M>= len(piles):
                return piles[startInd]
            
            bestChoice = float('inf')
            for X in range(1, 2*M + 1):
                newInd = startInd + X
                bestChoice = min(bestChoice, takeStone(newInd, max(X, M)))
            return piles[startInd] - bestChoice
        
        return takeStone(0, 1)
                        


class Solution:
    def stoneGameII(self, piles: List[int]) -> int:
        p = [0]
        cur = 0
        for i in piles:
            cur += i
            p.append(cur)
        
        n = len(piles)
        from functools import lru_cache
        @lru_cache(None)
        def dp(start, m):
            if start >= n: return 0
            return max(p[-1] - p[start] - dp(start+i, max(i,m)) for i in range(1,2*m+1))
        return dp(0,1)


class Solution:
    def stoneGameII(self, piles: List[int]) -> int:
        @functools.lru_cache(maxsize=None)
        def minimax(st, m, player):
            if st >= len(piles): return 0
            if player:
                return max([sum(piles[st:st+x]) + minimax(st+x, max(m,x), player^1) for x in range(1, 2*m+1)])
            else:
                return min([minimax(st+x, max(m,x), player^1) for x in range(1, 2*m+1)])
        return minimax(0, 1, 1) 

class Solution:
    def stoneGameII(self, piles: List[int]) -> int:
        n = len(piles)
        neg = -float(\"inf\")
        cache = [[0] * (n + 1) for _ in range(n + 1)]
        hasCache = [[False] * (n + 1) for _ in range(n + 1)]
        
        def get_result(index, M) -> int:
            if(index == n): 
                return 0
            if hasCache[index][M]:
                return cache[index][M]
            best = neg
            
            for i in range(1, 2*M + 1):
                num = sum(piles[index : index + i])
                score = num - get_result(min(index + i, n), min(max(i, M), n))
                best = max(best, score)
                
            hasCache[index][M] = True
            cache[index][M] = best
            return best
        
        total = sum(piles)
        delta = get_result(0, 1)
        return (total + delta) // 2

class Solution:
    def stoneGameII(self, piles: List[int]) -> int:
        @lru_cache(maxsize=None)
        def minimax(st, m, player):
            if st >= len(piles):
                return 0
            if player:
                return max([sum(piles[st:st+x]) + minimax(st+x, max(m, x), player^1) for x in range(1, 2*m+1) ])
            else:
                return min([minimax(st+x, max(m, x), player^1) for x in range(1, 2*m+1)])
        
        return minimax(0, 1, 1)


class Solution:
    def stoneGameII(self, piles: List[int]) -> int:
        
        self.piles = piles
        @lru_cache(maxsize=None)
        def helper(i, j, M, turn = True):
            
            if i>=j:
                return 0

            X = list(range(1,2*M+1))
            if turn:
                maxalex = -sys.maxsize
            else:
                maxalex = sys.maxsize
            for x in X:
                
                if turn:
                    if i+x <= j:
                        # print(\"Alex's turn\")
                        # print(\"Alex is picking - \", self.piles[i:i + x])
                        
                        alex = sum(self.piles[i:i + x]) + helper(i + x, j, max(x,M), turn=False)
                        maxalex = max(alex,maxalex)
                        # print(\"For \", i, \" turn, Alex got, \", alex)
                else:
                    # print(\"Lee's turn for \", i)
                    alex = helper(i + x, j, max(x,M), turn=True)
                    # print(\"After Lee picked in \", i, \" turn, Alex got \", alex)
                    maxalex = min(alex,maxalex)
                
                
                
            return maxalex
        
        return helper(0,len(self.piles),1)

class Solution:
    def stoneGameII(self, a: List[int]) -> int:
        @lru_cache(maxsize=None)
        def minimax(st, m, player):
            if st >= len(a): return 0
            if player:
                return max([sum(a[st:st+x]) + minimax(st+x, max(m,x), player^1) for x in range(1, 2*m+1)])
            else:
                return min([minimax(st+x, max(m,x), player^1) for x in range(1, 2*m+1)])
        return minimax(0, 1, 1) 

class Solution:
    def stoneGameII(self, piles: List[int]) -> int:
        @lru_cache(maxsize=None)
        def minimax(st, m, player):
            if st >= len(piles): return 0
            if player:
                return max([sum(piles[st:st+x]) + minimax(st+x, max(m,x), player^1) for x in range(1, 2*m+1)])
            else:
                return min([minimax(st+x, max(m,x), player^1) for x in range(1, 2*m+1)])
        return minimax(0, 1, 1)        

# [NOTE] Really good explanation here:
# https://leetcode.com/problems/stone-game-ii/discuss/345222/Python-Minimax-DP-solution
# The idea of minimax :
# If am the player 1 (whose winning sum we are trying to calculate), then I recurse on all possibilities and get the max.
# If am the player 2 (the opponent), then I try to minimize what P1 gets, and since we are not interested in what score P2 gets, we only calculate the min(all P1 next moves) and dont include the score P2 gets.
# Thanks to @douzigege for his comment which explains the minimax scenario specifically for this problem.

# if player == 1st player,
# gain = first x piles + minimax(..., 2nd player), where the gain is maximized
# if player == 2nd player,
# gain = 0 + minimax(..., 1st player), where the gain is minimized because the 2nd player tries to maximize this

# TLE for this input without@lru_cache
# [8270,7145,575,5156,5126,2905,8793,7817,5532,5726,7071,7730,5200,5369,5763,7148,8287,9449,7567,4850,1385,2135,1737,9511,8065,7063,8023,7729,7084,8407]


class Solution:
    def stoneGameII(self, a: List[int]) -> int:
        @lru_cache(maxsize=None)
        def minimax(st, m, player):
            if st >= len(a): return 0
            if player:
                return max([sum(a[st:st+x]) + minimax(st+x, max(m,x), player^1) for x in range(1, 2*m+1)])
            else:
                return min([minimax(st+x, max(m,x), player^1) for x in range(1, 2*m+1)])
        return minimax(0, 1, 1)   

class Solution:
    def stoneGameII(self, piles: List[int]) -> int:
        
        @lru_cache(maxsize=None)
        def minmax(st,m,player):
            if(st>=len(piles)):
                return 0
            if(player):
                return max([sum(piles[st:st+x])+minmax(st+x,max(x,m),player^1) for x in range(1,2*m+1)])
            else:
                return min([minmax(st+x, max(m,x), player^1) for x in range(1, 2*m+1)])
            
        return minmax(0,1,1)
        
        
        
#         piles=[0]+piles
        
#         self.p1=float('inf')
#         def traverse(piles,ind,ch,m,p1,p2):
#             print(ind,p1,p2)
#             if(ind==len(piles)):
#                 self.p1=min(p1,self.p1)
#             if(ch==1):
#                 su=0
#                 for i in range(ind,min(ind+2*m+1,len(piles))):
#                     su+=piles[i]
#                     traverse(piles,i+1,ch^1,max(m,i),p1+su,p2)
                    
#             else:
#                 su=0
#                 for i in range(ind,min(ind+2*m+1,len(piles))):
#                     su+=piles[i]
#                     traverse(piles,i+1,ch^1,max(m,i),p1,p2+su)
                
#         traverse(piles,1,1,1,0,0)
        
#         return self.p1


class Solution:
    def stoneGameII(self, piles: List[int]) -> int:
#         @lru_cache
#         def minimax(start, m, player):
#             if start >= len(piles):
#                 return 0
#             if player == 1:
#                 #Alex's turn
#                 return max(sum(piles[start:start + x]) + minimax(start + x ,max(x, m),2) for x in range(1, 2*m + 1))
#             if player == 2:
#                 return min(minimax(start + x, max(x, m), 1) for x in range(1, 2*m + 1))
        
#         return minimax(0, 1, 1)
        
                
                
                
                
                
                
        result = dict()
        result_min = dict()
        
        def minimax(start, M, player):
            if start >= len(piles):
                return 0
            if player == 1:
                # maxnum = -1
                if (start, M) in result:
                    return result[(start, M)]
                maxnum = -1
                for X in range(1, 2 * M + 1):
                    temp = minimax(start + X, max(X, M), 2) + sum(piles[start:start + X])
                    if temp > maxnum:
                        maxnum = temp
                result[(start, M)] = maxnum
                return maxnum
                
            if player == 2:
                #minimize
                minnum = 10^5
                if (start, M) in result_min:
                    return result_min[(start, M)]
                minnum = 1000000
                for X in range(1, 2 * M + 1):
                    temp = minimax(start + X, max(X, M), 1)
                    if temp < minnum:
                        minnum = temp
                result_min[(start, M)] = minnum
                return minnum
        res = minimax(0, 1, 1)
        print(result)
        print(result_min)
        return res


from functools import lru_cache
class Solution:
    def stoneGameII(self, piles: List[int]) -> int:
        
        n = len(piles)
        
        @lru_cache(maxsize = None)
        def dfs(index, M):
            if 2*M >= n - index:
                return sum(piles[index:])
            
            ret = float('inf')
            for X in range(1, 2*M + 1):
                if X > n - index:
                    break
                ret = min(ret, dfs(index + X, max(X, M)))
            
            return sum(piles[index:]) - ret
        
        return dfs(0, 1)
        
#         def dfs(index, M, order):
#             if 2*M >= n - index:
#                 if order % 2 == 1:
#                     return sum(piles[index:]), 0
#                 else:
#                     return 0, sum(piles[index:])
            
#             ret = [0, 0]
#             for x in range(1, 2*M + 1):
#                 if x > n - index:
#                     break
#                 a, b = dfs(index + x, max(x, M), (order + 1) % 2)
#                 if order % 2 == 1:
#                     # a += sum(piles[index:index+x])
#                     if a > ret[0]:
#                         ret[0] = a + sum(piles[index:index+x])
#                         ret[1] = b
#                 else:
#                     if b > ret[1]:
#                         # b += sum(piles[index:index+x])
#                         ret[0] = a
#                         ret[1] = b + sum(piles[index:index+x])
                        
#             return ret[0], ret[1]
        
#         return dfs(0, 1, 1)[0]


class Solution:
    def stoneGameII(self, piles: List[int]) -> int:
        
        def stoneGameIIUtil(piles: List[int], m: int, alex: bool) -> int:
            if not piles: return 0
            
            best = 0 if alex else 1000000
            for x in range(1, min(2 * m + 1, len(piles) + 1)):
                total = sum(piles[:x]) if alex else 0
                total += stoneGameIIUtil(piles[x:], max(m, x), not alex)
                best = max(best, total) if alex else min(best, total)
            return best
            
        return stoneGameIIUtil(piles, 1, True)

    def stoneGameII(self, piles: List[int]) -> int:
        
        lookup = {}
        def stoneGameIIUtil(piles: List[int], m: int, alex: bool) -> int:
            if not piles: return 0
            if (tuple(piles), m, alex) in lookup:
                return lookup[(tuple(piles), m, alex)]
            
            best = 0 if alex else 1000000
            for x in range(1, min(2 * m + 1, len(piles) + 1)):
                total = sum(piles[:x]) if alex else 0
                total += stoneGameIIUtil(piles[x:], max(m, x), not alex)
                best = max(best, total) if alex else min(best, total)
            lookup[(piles, m, alex)] = best
            return best
            
        return stoneGameIIUtil(tuple(piles), 1, True)

class Solution:
    def stoneGameII(self, piles: List[int]) -> int:
        # @lru_cache(maxsize=None)
        # def minimax(st, m, player):
        #     if st >= len(piles): return 0
        #     if player:
        #         return max([sum(piles[st:st+x]) + minimax(st+x, max(m,x), player^1) for x in range(1, 2*m+1)])
        #     else:
        #         return min([minimax(st+x, max(m,x), player^1) for x in range(1, 2*m+1)])
        # # print()
        # return minimax(0, 1, 1)   
        result = dict()
        result_min = dict()
        
        def minimax(start, M, player):
            if start >= len(piles):
                return 0
            if player == 1:
                # maxnum = -1
                if (start, M) in result:
                    return result[(start, M)]
                maxnum = -1
                for X in range(1, 2 * M + 1):
                    temp = minimax(start + X, max(X, M), 2) + sum(piles[start:start + X])
                    if temp > maxnum:
                        maxnum = temp
                result[(start, M)] = maxnum
                return maxnum
                
            if player == 2:
                #minimize
                minnum = 10^5
                if (start, M) in result_min:
                    return result_min[(start, M)]
                minnum = 1000000
                for X in range(1, 2 * M + 1):
                    temp = minimax(start + X, max(X, M), 1)
                    if temp < minnum:
                        minnum = temp
                result_min[(start, M)] = minnum
                return minnum
        res = minimax(0, 1, 1)
        print(result)
        print(result_min)
        return res


class Solution:
    def stoneGameII(self, piles: List[int]) -> int:
        s = 0
        for i in range(len(piles)-1,-1,-1):
            s+=piles[i]
            piles[i] = s
        
        def bt(m,player,M,remain,spiles):
            if remain <= 0 :
                return 0
            
            key = (player,M,remain)
            if key in m:
                return m[key]
            
            res = 0
            for take in range(1,2*M+1):
                index = len(piles) - remain
                res = max(res, spiles[index] - bt(m,1-player,max(M, take), remain - take,spiles))
                
            m[key] = res
            return res
        
        return bt({},0,1,len(piles),piles)

class Solution:
    def stoneGameII(self, A: List[int]) -> int:
        n = len(A)
        memo = {}
        def take(i, m, alex):
            if i >= len(A):
                return 0
            
            if (i, m, alex) in memo:
                return memo[(i, m, alex)]
            
            if alex:
                res = 0
                taking = 0
                for x in range(1, min(n,2*m + 1)):
                    if i+x-1 < n:
                        taking += A[i+x-1]
                    res = max(res, taking + take(i+x, max(m, x), False))
            else:
                res = sum(A[i:])
                for x in range(1, min(n,2*m + 1)):
                    res = min(res, take(i+x, max(m,x), True))
            
            memo[(i, m, alex)] = res
            
            return res
        return take(0, 1, True)
                
                
                    


class Solution:
    def stoneGameII(self, piles: List[int]) -> int:
        l = len(piles)
        dp = [[[-1 for i in range(l)] for j in range(2*l)] for k in range(2)]
        
        def game(piles, M, pos, player):
            total = 0
            if pos >= l:
                return 0
            if dp[player][pos][M] != -1:
                return dp[player][pos][M]
            if player == 0:
                maxsum = 0
                for X in range(1, 2 * M + 1):
                    maxsum = max(maxsum, sum(piles[pos:pos+X]) + game(piles, max(M, X), pos+X, not player))
                
                dp[player][pos][M] = maxsum   
                return maxsum
            else:
                minsum = sys.maxsize
                for X in range(1, 2 * M + 1):
                    minsum = min(minsum, game(piles, max(M, X), pos + X, not player))
                dp[player][pos][M] = minsum

                if minsum == sys.maxsize:
                    return 0
                
                
                return minsum  
            

        return game(piles, 1, 0, 0)
            


class Solution:
    def stoneGameII(self, piles: List[int]) -> int:
        def pick_stones(i,m,t):
            '''
            m -> player can pick 1<=X<=2M piles
            t -> player 1's turn if true else 0
            '''
            if i>=len(piles):
                return 0
            if (i,m,t) in d:
                return d[(i,m,t)]
            if t:
                d[(i,m,t)]=max(pick_stones(i+k,max(m,k),False)+sum(piles[i:i+k]) for k in range(1,2*m+1))
            else:
                d[(i,m,t)]=min(pick_stones(i+k,max(m,k),True) for k in range(1,2*m+1))
            return d[(i,m,t)]
        d={}
        return pick_stones(0,1,True)

class Solution:
    def stoneGameII(self, piles: List[int]) -> int:
        
        @lru_cache(maxsize=None)
        def minmax(st,m,player):
            if(st>=len(piles)):
                return 0
            if(player):
                return max([sum(piles[st:st+x])+minmax(st+x,max(x,m),player^1) for x in range(1,2*m+1)])
            else:
                return min([minmax(st+x, max(m,x), player^1) for x in range(1, 2*m+1)])
        return minmax(0,1,1)
        
        
        
#         piles=[0]+piles
        
#         self.p1=float('inf')
#         def traverse(piles,ind,ch,m,p1,p2):
#             print(ind,p1,p2)
#             if(ind==len(piles)):
#                 self.p1=min(p1,self.p1)
#             if(ch==1):
#                 su=0
#                 for i in range(ind,min(ind+2*m+1,len(piles))):
#                     su+=piles[i]
#                     traverse(piles,i+1,ch^1,max(m,i),p1+su,p2)
                    
#             else:
#                 su=0
#                 for i in range(ind,min(ind+2*m+1,len(piles))):
#                     su+=piles[i]
#                     traverse(piles,i+1,ch^1,max(m,i),p1,p2+su)
                
#         traverse(piles,1,1,1,0,0)
        
#         return self.p1


class Solution:
    # 0123
    def playerGame(self, pos, piles, player1, M,memo):
        optionsCount = min (len(piles) - pos, 2*M)
        #print (optionsCount)
        resultPlayer1 = 0
        resultPlayer2 = 0
        for i in range(pos, pos + optionsCount):
            X = i -pos + 1
            #print (X)
            stonesCount = 0
            for j in range(pos,i+1):
                stonesCount +=piles[j]
            combination = (i+1,not player1, max(M,X))
            if combination in memo:
                count1, count2 = memo[combination]
            else:
                count1,count2 = self.playerGame(i +1, piles, not player1, max(M,X),memo)
                memo[combination] = [count1,count2]
            if player1:
                if stonesCount + count1 > resultPlayer1:
                    resultPlayer1 = stonesCount + count1
                    resultPlayer2 = count2
            else:
                if stonesCount + count2 > resultPlayer2:
                    resultPlayer1 = count1
                    resultPlayer2 = stonesCount + count2
        return resultPlayer1,resultPlayer2 
 
        
    def stoneGameII(self, piles: List[int]) -> int:
        #get max number of stones for Alex 
        M=1
        player1 = True
        memo = {}
        pos = 0
        return self.playerGame(pos,piles, player1, M, memo)[0]

                
            


class Solution:
    def stoneGameII(self, A: List[int]) -> int:
        
        
        
        # my solution ... 96 ms ... 51 % ... 14.9 MB ... 25 %
        #  time: O()
        # space: O()
        
        seen = {}
        def max_stones(sidx, m):  # 返回面对 A[sidx:] 时，直至游戏结束，所能取到的最多石头
            if sidx == len(A):
                return 0
            if (sidx, m) not in seen:
                if len(A)-sidx <= 2*m:
                    seen[sidx, m] = endsum[sidx]  # sum(A[sidx:])
                else:
                    res = 0
                    for x in range(1, 2*m+1):
                        new_sidx = sidx + x
                        res = max(res, endsum[sidx] - max_stones(new_sidx, max(m, x)))
                    seen[sidx, m] = res
            return seen[sidx, m]
        
        endsum = [A[-1]]*len(A)
        for j in range(len(A)-2, -1, -1):
            endsum[j] = A[j] + endsum[j+1]
        return max_stones(0, 1)
        
        


class Solution:
    def stoneGameII(self, piles: List[int]) -> int:
        def pick_stones(i,m,t):
            '''
            m -> player can pick 1<=X<=2M piles
            t -> player 1's turn if true else 0
            '''
            if i>=len(piles):
                return 0
            if (i,m,t) in d:
                return d[(i,m,t)]
            if t:
                d[(i,m,t)]=max(pick_stones(i+k,max(m,k),1-t)+sum(piles[i:i+k]) for k in range(1,2*m+1))
            else:
                d[(i,m,t)]=min(pick_stones(i+k,max(m,k),1-t) for k in range(1,2*m+1))
            return d[(i,m,t)]
        d={}
        return pick_stones(0,1,True)

class Solution:
    def stoneGameII(self, piles: List[int]) -> int:
        memo = {}
        n = len(piles)
        
        def dfs(player, start, m):
            if (player, start, m) in memo:
                return memo[(player, start, m)]
            
            cur = 0
            res = 0
            aj = i = start
            am = m
            
            while i < n and i - start + 1 <= 2 * m:
                cur += piles[i]
                _, bj, bm = dfs(1 - player, i + 1, max(i - start + 1, m))
                if res < cur + dfs(player, bj + 1, bm)[0]:
                    res = cur + memo[(player, bj + 1, bm)][0]
                    aj = i
                    am = max(i - start + 1, m)
                    
                i += 1
            
            memo[(player, start, m)] = (res, aj, am)
            return res, aj, am
        
        return dfs(0, 0, 1)[0]


class Solution:
    def stoneGameII(self, piles: List[int]) -> int:
        @lru_cache(None)
        def dp(idx,M,people):
            if idx>=len(piles):
                return 0
            res=[]
            for X in range(1,2*M+1,1):
                res.append(dp(idx+X,max(M,X),1 if people==0 else 0)+people*sum(piles[idx:idx+X]))
            if people==1:
                return max(res)
            else:
                return min(res)
        return dp(0,1,1)
                


MIN = float('-inf')
class Solution:
    def stoneGameII(self, piles):
        
        def dfs(start, M, memo):
            if start == len(piles):
                return 0
            if (start,M) in memo:
                return memo[(start,M)]
            max_diff = MIN
            for X in range(1, 2*M+1):
                cur, end = 0, min(len(piles), start+X)
                for i in range(start, end):
                    cur += piles[i]
                max_diff = max(max_diff, cur-dfs(end, max(M,X), memo))
            memo[(start,M)] = max_diff
            return max_diff
        
        total = sum(piles)
        return (dfs(0, 1, {})+total) // 2
        


class Solution:
    def stoneGameII(self, a: List[int]) -> int:
        @lru_cache(maxsize=None)
        def minimax(start, m, alex):
            if start >= len(a): return 0
            if alex:
                return max([sum(a[start:start+x]) + minimax(start+x, max(m,x), (not alex)) for x in range(1, 2*m+1)])
            else:
                return min([minimax(start+x, max(m,x), (not alex)) for x in range(1, 2*m+1)])
        return minimax(0, 1, True)
        
        
        
        


class Solution:
    def stoneGameII(self, piles: List[int]) -> int:
      N = len(piles)
      @lru_cache(maxsize=None)
      def recurse(idx, m, alexTurn):
        # print(f\"RECURSE {idx} {m} {alexTurn}\")
        if idx > N-1:
          return (0, 0)
        ops = []
        for x in range(1, 2*m+1):
          curNumStones = sum(piles[idx:idx+x])
          (nextA, nextL) = recurse(idx+x, max(m, x), not alexTurn)
          # nextA = nxt[0]
          # nextL = nxt[1]
          if alexTurn:
            ops.append((nextA+curNumStones, nextL))
          else:
            ops.append((nextA, nextL+curNumStones))
        [aScores, lScores] = list(zip(*ops)) 
        # aScores = [x[0] for x in ops]
        # lScores = [x[1] for x in ops]
        if alexTurn:
          return (max(aScores), max(lScores))
        else:
          return (min(aScores), max(lScores))
      return recurse(0, 1, True)[0]
    
    \"\"\"
    recurse(0, 1, True) -> 
      2 + recurse(1, 1, False) 
        recurse(1, 1, False) -> 
          9 + recurse(2, 1, True) 
          9 + 4 + recurse(3, 2, True)
      9 + recurse(2, 2, False)
          
    \"\"\"

class Solution:
    def stoneGameII(self, piles: List[int]) -> int:
        self.arr = piles
        self.dp = {}
        ans = self.helper(0,1,1)
        print(self.dp)
        return ans
        
    def helper(self, i, m, turn):
        if(i >= len(self.arr)):
            return 0
        
        if((i,m,turn) in self.dp):
            return self.dp[(i,m,turn)]
        
        if(turn):
            ans = []
            for x in range(2*m):
                tmp = sum(self.arr[i:i+x+1]) + self.helper(i+x+1, max(x+1,m), 0)
                ans.append(tmp)
            self.dp[(i,m,turn)] = max(ans)
            return self.dp[(i,m,turn)]
        
        else:
            ans = []
            for x in range(2*m):
                tmp = self.helper(i+x+1, max(x+1,m), 1)
                ans.append(tmp)
            self.dp[(i,m,turn)] = min(ans)
            return self.dp[(i,m,turn)]

class Solution:
    # opt[M][i] = max(sum(pile[i:i+m]) + sum[piles[i:]] - opt[max(m,M)][i+m]) for all m 1->2M
    def stoneGameII(self, piles: List[int]) -> int:
        if len(piles) == 1:
            return piles[0]
        pileCount = len(piles)
        scores = [[0 for y in range(0, len(piles))] for x in range(0,len(piles))]
        # print(scores)
        for i in range(len(scores)-1, -1, -1):
            for M in range(1, len(scores[i])):
                # print(\"indexes: \" + str(i) + \" , \" + str(M))
                if i + 2*M >= pileCount:
                    scores[i][M] = sum(piles[i:])
                else:
                    m_options = [sum(piles[i:i+m]) + sum(piles[i+m:]) - scores[0 if i+m > pileCount else i+m][max(m, M)] for m in range(1, 2*M + 1)]
                    # if i == 2 and M == 1:
                    #     print(sum(piles[i:i+1]))
                    #     print(sum(piles[i+1:]))
                    #     print(scores[0 if i+1 > pileCount else i+1][max(1, M)])
                    
                    # print(m_options)
                    scores[i][M] = max(m_options)
                # print(\"score grid: \")
                # for row in scores:
                #     print(row)
        return scores[0][1]

class Solution:
    def stoneGameII(self, piles: List[int]) -> int:
        presum=list(piles)
        for i in range(1,len(piles)):
            presum[i]+=presum[i-1]
          
        from functools import lru_cache
        @lru_cache(None)
        def dp(ind,m):
            if ind+2*m>=len(piles): return presum[-1]-(presum[ind-1] if ind>0 else 0)
            sm=float('-inf')
            for i in range(1,2*m+1):
                me = presum[ind+i-1]-(presum[ind-1] if ind>0 else 0)
                sm = max(sm, me + presum[-1]-presum[ind+i-1] - dp(ind+i,max(m,i)))
            return sm
        
        return dp(0,1)

class Solution:
    def stoneGameII(self, piles: List[int]) -> int:
      N = len(piles)
      @lru_cache(maxsize=None)
      def recurse(idx, m, alexTurn):
        # print(f\"RECURSE {idx} {m} {alexTurn}\")
        if idx > N-1:
          return (0, 0)
        ops = []
        for x in range(1, 2*m+1):
          curNumStones = sum(piles[idx:idx+x])
          (nextA, nextL) = recurse(idx+x, max(m, x), not alexTurn)
          # nextA = nxt[0]
          # nextL = nxt[1]
          if alexTurn:
            ops.append((nextA+curNumStones, nextL))
          else:
            ops.append((nextA, nextL+curNumStones))
        aScores = [x[0] for x in ops]
        lScores = [x[1] for x in ops]
        if alexTurn:
          return (max(aScores), max(lScores))
        else:
          return (min(aScores), max(lScores))
      return recurse(0, 1, True)[0]
    
    \"\"\"
    recurse(0, 1, True) -> 
      2 + recurse(1, 1, False) 
        recurse(1, 1, False) -> 
          9 + recurse(2, 1, True) 
          9 + 4 + recurse(3, 2, True)
      9 + recurse(2, 2, False)
          
    \"\"\"

#1 DP (Top-down with memoization)
class Solution:
    def stoneGameII(self, piles: List[int]) -> int:
        if len(piles) <= 2:
            return sum(piles)
        n = len(piles)
        # Compute suffix sum
        for i in range(n - 2, -1, -1):
            piles[i] += piles[i + 1]
        piles.append(0)
        
        dp = [[0] * (n + 1) for _ in range(n + 1)]
        
        for pile in reversed(range(n)):
            for M in reversed(range(n)):
                nextPlayerMaximum = piles[pile]
                for nextPile in range(pile + 1, min(pile + 2 * M + 1, n + 1)):
                    nextPlayerMaximum = min(nextPlayerMaximum, dp[nextPile][max(M, nextPile - pile)])
                dp[pile][M] = piles[pile] - nextPlayerMaximum
        
        return dp[0][1]

# So the basic idea here is that there is no reason to have separate sum_alex and sum_lee variables, because they both sum up to suffix_sum[pile]
# Here is an example (X - we haven't desided yet, A - taken by Alex, L - taken by Lee)

# XXXXXXXXXXAALAAALLLAALA
#           ^
# \t\t  pile
# From this you can see that in order to calculate the number of piles taken by this player so far we just substract the number of the piles taken by another player from the total number of piles up to the current pile position.
# The next important thing to notice is that minimizing sum for the one player leads to maximising it for another and vice versa.
# This leads us to conclusion that we can do the same with just a single variable sum_next_player.
# The alrorightm now looks the following way:

# We're trying to pick up to 2 * M piles from the current position and pass the turn to the next player
# We're getting back from the next player the maximum sum they were able to get and trying to minimize it
# Now when we found the minimum sum for the other player that also means we found the maximum sum for us, so return it
# That's how we got to the nice and short Top-Down DP solution.
# The only thing left - convert it to Bottom-Up solution to make the interviewer happy. And here is it

class Solution:
    @staticmethod
    def _suffix_sum(piles: List[int]) -> List[int]:
        suffix_sum = [0]

        for pile in reversed(piles):
            suffix_sum.append(suffix_sum[-1] + pile)

        suffix_sum.reverse()

        return suffix_sum
    
    def stoneGameII(self, piles: List[int]) -> int:
        suffix_sum = self._suffix_sum(piles)

        dp = [[0] * (len(piles) + 1) for _ in range(len(piles) + 1)]

        for pile in reversed(range(len(piles))):
            for M in reversed(range(len(piles))):
                sum_next_player = suffix_sum[pile]

                for next_pile in range(pile + 1, min(pile + 2 * M + 1, len(piles) + 1)):
                    sum_next_player = min(
                        sum_next_player, dp[next_pile][max(M, next_pile - pile)]
                    )

                sum_player = suffix_sum[pile] - sum_next_player

                dp[pile][M] = sum_player

        return dp[0][1]

#1 DP (Top-down with memoization)
#2 DP (Bottom-up)

# Is better to work recurrence relation from back to start, dfs(i, M) = suffix_sum[i] - max(dfs(i + j, max(M, j)) for i in range(1, min(2M + 1, remaining length of piles)))
class Solution:
    def stoneGameII(self, piles: List[int]) -> int:
        if len(piles) <= 2:
            return sum(piles)
        n = len(piles)
        # Compute suffix sum
        for i in range(n - 2, -1, -1):
            piles[i] += piles[i + 1]
        piles.append(0)
        
        dp = [[0] * (n + 1) for _ in range(n + 1)]
        
        for pile in reversed(range(n)):
            for M in reversed(range(n)):
                nextPlayerMaximum = piles[pile]
                for nextPile in range(pile + 1, min(pile + 2 * M + 1, n + 1)):
                    nextPlayerMaximum = min(nextPlayerMaximum, dp[nextPile][max(M, nextPile - pile)])
                dp[pile][M] = piles[pile] - nextPlayerMaximum
        
        return dp[0][1]

class Solution:
    def stoneGameII(self, piles: List[int]) -> int:
        
        M = (len(piles)+1)//2
        record = [[0 for _ in range(len(piles))] for _ in range(M)]
        total = [0 for _ in range(len(piles))]
        for i in range(M):
            record[i][-1] = piles[-1] 
        total[-1] = piles[-1]
        
        for i in range(len(piles)-2, -1, -1):
            total[i] = total[i+1] + piles[i]
        
        for i in range(len(piles)-2, -1, -1):
            for j in range(M):
                   min_num = float(inf)
                   for k in range(2*(j+1)):
                       if i+k+1 >= len(piles):
                          if min_num > 0:
                                min_num = 0
                       else:
                           if record[min(max(j, k), M-1)][i+k+1] < min_num:
                               min_num = record[min(max(j, k), M-1)][i+k+1]
                    
                   record[j][i] = total[i] - min_num
        print(record)
        return record[0][0]

class Solution:
    def stoneGameII(self, piles: List[int]) -> int:
        N = len(piles)
        self.dp = {}
        
        def recursiveStoneGame(start, M):            
            if start >= N:
                return 0
            
            if start == N-1:
                return piles[start]
            
            if (start, M) in self.dp:
                return self.dp[(start, M)]

            alex = 0
            for x in range(1, 2*M+1):
                opponent_score = recursiveStoneGame(start+x, max(x, M))
                this_score = sum(piles[start:]) - opponent_score
                
                alex = max(alex, this_score)
                
            self.dp[(start, M)] = alex
                
            return alex
        
        
        result = recursiveStoneGame(0, 1)
        return result

class Solution:
    def solve(self, start, end, M, player):
        if (start,end,M,player) in self.dp:
            return self.dp[start,end,M,player]
        maxa = 0
        maxl = 0
        if start > end:
            return [0,0]
        
        for i in range(1,  2*M+1):
            picked = sum(self.piles[start:start+i])
            if player == 0:
                a,l = self.solve(start+i, end, max(i,M), 1)
                if picked + a > maxa:
                    maxa = picked + a
                    maxl = l
            else:
                a,l = self.solve(start+i, end, max(i,M), 0)
                if picked + l > maxl:
                    maxa = a
                    maxl = picked + l
                
        self.dp[(start,end,M,player)] = (maxa, maxl)
        return (maxa, maxl)
    
    def stoneGameII(self, piles: List[int]) -> int:
        self.dp = {}
        self.piles = piles
        
        ans = self.solve(0, len(piles)-1, 1, 0)
        print(self.dp)
        return ans[0]

class Solution:
    def helper(self, n, M, curr, piles, memo):
        if curr >= n:
            return 0
        
        if n - curr <= 2*M:
            return sum(piles[curr:])
        
        if (curr, M) in memo:
            return memo[(curr, M)]
        
        me = 0
        total = sum(piles[curr:])
        
        for X in range(1, 2*M + 1):
            opponent = self.helper(n, max(X, M), curr + X, piles, memo)
            
            me = max(me, total - opponent)
            
        memo[(curr, M)] = me
        
        return me
    def stoneGameII(self, piles: List[int]) -> int:
        return self.helper(len(piles), 1, 0, piles, {})

class Solution:
    def stoneGameII(self, piles: List[int]) -> int:
        n = len(piles)

        memo = {}
        def dft(i, m, p):
            if i >= n: return [0, 0]
            if (i, m, p) in memo:
                return list(memo[(i, m, p)])
            score = [0, 0]
            for x in range(1, 2 * m + 1):
                s = sum(piles[i:i+x])
                forward = dft(i + x, max(m, x), (p + 1) % 2)
                forward[p] += s
                if forward[p] > score[p]:
                    score = forward
            memo[(i, m, p)] = list(score)
            return score

        return dft(0, 1, 0)[0]


class Solution:
    def stoneGameII(self, piles: List[int]) -> int:
        self.piles = piles
        self.memo = {} # map of (start, M, is_player_1) to int
        return self.minimax(0, 1, True)
    
    def minimax(self, start: int, M: int, is_player_1: bool) -> int:
        if start >= len(self.piles):
            return 0
        if (start, M, is_player_1) in self.memo:
            return self.memo[(start, M, is_player_1)]
        if is_player_1:
            output = max([
                sum(self.piles[start:start + x]) + self.minimax(start + x, max(x, M), False) 
                for x in range(1, min(2 * M, len(self.piles)) + 1)
            ])
        else:
            output = min([
                self.minimax(start + x, max(x, M), True) 
                for x in range(1, min(2 * M, len(self.piles)) + 1)
            ])
        self.memo[(start, M, is_player_1)] = output
        return output

class Solution:
    def stoneGameII(self, piles: List[int]) -> int:
        N = len(piles)
        suffix_sum = [0] * N
        
        running_sum = 0
        for idx in range(N-1, -1, -1):
            running_sum += piles[idx]
            suffix_sum[idx] = running_sum
            
        DP = [[0]*(N+1) for _ in range(N+1)]
        
        for pile_no in reversed(list(range(N))):
            for M in reversed(list(range(N))):
                min_next_player = suffix_sum[pile_no]
                for x in range(1, min(2*M + 1, N+1)):
                    if pile_no + x < N:
                        min_next_player = min(min_next_player, DP[pile_no + x][max(x,M)])
                    else:
                        min_next_player = 0
                DP[pile_no][M] = suffix_sum[pile_no] - min_next_player
            
        return DP[0][1]
        
#         # @lru_cache(None)
#         def dfs(pile_no, M):
#             if pile_no > N-1:
#                 return 0
#             if DP[pile_no][M] > 0:
#                 return DP[pile_no][M]
#             min_next_player = suffix_sum[pile_no]
#             for x in range(1, min(2*M + 1, N+1)):
#                 min_next_player = min(min_next_player, dfs(pile_no + x, max(x,M)))
                
#             DP[pile_no][M] = suffix_sum[pile_no] - min_next_player
#             return DP[pile_no][M]
            
#         return dfs(0, 1)
        
            
        
        
        
        
            


class Solution:
    def stoneGameII(self, piles: List[int]) -> int:
        N = len(piles)
        INF = float(\"inf\")
        
        dp = [[0]*(N+1) for _ in range(N+1)]
        isComputed = [[False]*(N+1) for _ in range(N+1)]
        
        def getMaxScore(index, M):
            if index == N:
                return 0
            if isComputed[index][M]:
                return dp[index][M]
            
            bestScore = -INF
            
            for X in range(1, 2*M + 1):
                stones = sum(piles[index:index+X])
                score = stones - getMaxScore(min(index+X,N), min(max(M,X),N))
                
                bestScore = max(bestScore,score)
                
                
            isComputed[index][M] = True
            dp[index][M] = bestScore
            
            return bestScore
        
        # total = my score + opponent score
        # delta = my score - opponent score
        total = sum(piles)
        delta = getMaxScore(0,1)
        return (total + delta)//2
        

from functools import lru_cache
class Solution:
    def stoneGameII(self, piles: List[int]) -> int:
        
        def alex(idx, M, score_alex, score_lee):
            #print('alex', idx, M, score_alex, score_lee)
            if idx == len(piles):
                return score_alex, score_lee
            if idx == len(piles)-1:
                return score_alex + piles[idx], score_lee
            maxa, countl = score_alex, score_lee
            for i in range(1, 2*M+1):
                if idx+i <= len(piles):
                    sa, sl = lee(idx+i, i, score_alex + sum(piles[idx:idx+i]), score_lee)
                    if maxa < sa:
                        maxa = sa
                        countl = sl
                else:
                    break
            #print('--------> alex', idx, M, maxa, countl)
            return maxa, countl 
            
        
        def lee(idx, M, score_alex, score_lee):
            #print('lee', idx, M, score_alex, score_lee)
            if idx == len(piles):
                return score_alex, score_lee
            if idx == len(piles)-1:
                return score_alex, score_lee + piles[idx]
            counta, maxl = score_alex, score_lee
            for i in range(1, 2*M+1):
                if idx+i <= len(piles):
                    sa, sl = alex(idx+i, i, score_alex, score_lee + sum(piles[idx:idx+i]))
                    if maxl < sl:
                        maxl = sl
                        counta = sa
                else:
                    break
            #print('--------> lee', idx, M, maxl, counta)
            return counta, maxl
        
        #self.memo = dict()
        #return alex(0, 1, 0, 0)[0]
        
        @lru_cache(None)
        def minimax(i, m, player):
            if i >= len(piles): return 0
            if player == 0:
                return max(sum(piles[i:i+j]) + minimax(i+j, max(m,j), player^1) for j in range(1, 2*m+1))
            else:
                return min(minimax(i+j, max(m,j), player^1) for j in range(1, 2*m+1))
        return minimax(0, 1, 0)   

from collections import defaultdict
class Solution:
    def stoneGameII(self, piles: List[int]) -> int:
        N=len(piles)

        dp=defaultdict(dict)
        M=1
        return self.DP(N,dp,piles,M,0)

        
    def DP(self,n,dp,piles,M,start):
        if n<=2*M:
            return sum(piles[start:])
        if n in dp and M in dp[n]:
            return dp[n][M]
        
        res=float('-inf')
        
        for x in range(1,2*M+1):
            newM=max(x,M)
            if n-x<=2*newM:
                res2=0
            else:
                res2=float('inf')
                for y in range(1,2*newM+1):
                    newM2=max(y,newM)
                    res2=min(res2,self.DP(n-x-y,dp,piles,newM2,start+x+y)) 

            res=max(res, res2 + sum(piles[start:start+x]) )
             
        dp[n][M]=res 
                        
        return res
            
                
            
            
        
        
        
        



class Solution:
    def stoneGameII(self, piles: List[int]) -> int:
        N = len(piles)
        suffix_sum = [0] * N
        
        running_sum = 0
        for idx in range(N-1, -1, -1):
            running_sum += piles[idx]
            suffix_sum[idx] = running_sum
            
        DP = [[0]*(N) for _ in range(N)]
        
        for pile_no in reversed(list(range(N))):
            for M in reversed(list(range(N))):
                min_next_player = suffix_sum[pile_no]
                for x in range(1, min(2*M + 1, N+1)):
                    if pile_no + x < N:
                        min_next_player = min(min_next_player, DP[pile_no + x][max(x,M)])
                    else:
                        min_next_player = 0
                DP[pile_no][M] = suffix_sum[pile_no] - min_next_player
            
        return DP[0][1]
        
#         # @lru_cache(None)
#         def dfs(pile_no, M):
#             if pile_no > N-1:
#                 return 0
#             if DP[pile_no][M] > 0:
#                 return DP[pile_no][M]
#             min_next_player = suffix_sum[pile_no]
#             for x in range(1, min(2*M + 1, N+1)):
#                 min_next_player = min(min_next_player, dfs(pile_no + x, max(x,M)))
                
#             DP[pile_no][M] = suffix_sum[pile_no] - min_next_player
#             return DP[pile_no][M]
            
#         return dfs(0, 1)
        
            
        
        
        
        
            


from collections import defaultdict
class Solution:
    def stoneGameII(self, piles: List[int]) -> int:
        N=len(piles)
        # dp=[[-1 for _ in range(N)] for _ in range(2)]
        dp=defaultdict(int)
        M=1
        return self.DP(N,dp,piles,M,0)

        
    def DP(self,n,dp,piles,M,start):
        if n<=2*M:
            return sum(piles[start:])
        if (n,M) in dp:
            return dp[(n,M)]
        
        res=float('-inf')
        
        for x in range(1,2*M+1):
            newM=max(x,M)
            if n-x<=2*newM:
                res2=0
            else:
                res2=float('inf')
                for y in range(1,2*newM+1):
                    newM2=max(y,newM)
                    res2=min(res2,self.DP(n-x-y,dp,piles,newM2,start+x+y)) 

            res=max(res, res2 + sum(piles[start:start+x]) )

                
        dp[(n,M)]=res 
                        
        return dp[(n,M)]
            
                
            
            
        
        
        
        



import numpy

# bruteforce
def gobf(piles, i, m, alex):
    res = 0 if alex == 1 else float(\"inf\")
    if i == len(piles):
        return 0
        
    for x in range(1, 2 * m + 1):
        if i + x > len(piles):
            break
        if alex == 1:
            res = max(res, sum(piles[i:i+x]) + gobf(piles, i+x, max(x,m), 0))
        else:
            res = min(res, gobf(piles, i+x, max(x,m), 1))
    return res


# memo
def go(piles, i, m, alex, memo):
    if i == len(piles):
        return 0
    if memo[i][m][alex] != -1:
        return memo[i][m][alex]
        
    res = 0 if alex == 1 else float(\"inf\")
    for x in range(1, 2 * m + 1):
        if i + x > len(piles):
            break
        if alex == 1:
            res = max(res, sum(piles[i:i+x]) + go(piles, i+x, max(x,m), 0, memo))
        else:
            res = min(res, go(piles, i+x, max(x,m), 1, memo))
    memo[i][m][alex] = res
    return memo[i][m][alex]

class Solution:
    def stoneGameII(self, piles: List[int]) -> int:
        n = len(piles)
        memo = numpy.ndarray((n, n + 1, 2), int)
        memo.fill(-1)
        return go(piles, 0, 1, 1, memo)

\"\"\"
dp[i][j] = the max score one can get with [i:] piles and M = j.
dp[i][j] = max(sum[i:x] for x in range(1, min(2*M, n) - dp[i+x][max(M, x)])
dp[i][n] = sum(piles[i:])
\"\"\"
class Solution:
    def stoneGameII(self, piles: List[int]) -> int:
        n = len(piles)
        suf_sum = [0 for _ in range(n + 1)]
        for i in range(n - 1, -1, -1):
            suf_sum[i] = suf_sum[i+1] + piles[i]
            
        dp = [[0 for _ in range(n + 1)] for _ in range(n + 1)]
        for i in range(n + 1):
            dp[i][n] = suf_sum[i]
        
        for i in range(n, -1, -1):
            for j in range(n, 0, -1):
                for x in range(1, min(2*j, n - i) + 1):
                    dp[i][j] = max(dp[i][j], suf_sum[i] - dp[i+x][max(j, x)])
        return dp[0][1]