Alex and Lee play a game with piles of stones.  There are an even 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.  The total number of stones is odd, so there are no ties.
Alex and Lee take turns, with Alex starting first.  Each turn, a player takes the entire pile of stones from either the beginning or the end of the row.  This continues until there are no more piles left, at which point the person with the most stones wins.
Assuming Alex and Lee play optimally, return True if and only if Alex wins the game.
 
Example 1:
Input: piles = [5,3,4,5]
Output: true
Explanation: 
Alex starts first, and can only take the first 5 or the last 5.
Say he takes the first 5, so that the row becomes [3, 4, 5].
If Lee takes 3, then the board is [4, 5], and Alex takes 5 to win with 10 points.
If Lee takes the last 5, then the board is [3, 4], and Alex takes 4 to win with 9 points.
This demonstrated that taking the first 5 was a winning move for Alex, so we return true.

 
Constraints:

2 <= piles.length <= 500
piles.length is even.
1 <= piles[i] <= 500
sum(piles) is odd.

Difficulty: interview

Starter code:

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


Solutions:
class Solution:
    def stoneGame(self, piles: List[int]) -> bool:
        return True

class Solution:
    def stoneGame(self, piles: List[int]) -> bool:
        return 1;


class Solution:
    def recur(self,i,j,piles,n,dp,s):
        if j==i+1:
            return max(piles[i],piles[j])
        if dp[i+1][j] != -1:
            l = dp[i+1][j]
        else:    
            l = self.recur(i+1,j,piles,n,dp,s-piles[i])
        if dp[i][j-1] !=-1:
            r = dp[i][j-1]
        else:    
            r = self.recur(i,j-1,piles,n,dp,s-piles[j])
            
        ans =  max(s-l,s-r)
        dp[i][j] = ans
        return ans
    def stoneGame(self, piles: List[int]) -> bool:
        n = len(piles)
        dp = [[-1 for i in range(n+1)] for j in range(n+1)]
        m = (self.recur(0,n-1,piles,n,dp,sum(piles)))
    
        if m>sum(piles)-m:
            return True
        else:
            return False
        


class Solution:
    def stoneGame(self, piles: List[int]) -> bool:
        @lru_cache(None)
        def dp(i, j):
            if i > j: return 0
            if (j - i + 1) % 2 == 0:
                return max(piles[i] + dp(i + 1, j), piles[j] + dp(i, j - 1))
            else:
                return max(-piles[i] + dp(i + 1, j), -piles[j] + dp(i, j - 1))
        return dp(0, len(piles) - 1) > 0
            


class Solution:
    def stoneGame(self, piles: List[int]) -> bool:
        @lru_cache(None)
        def dfs(i, j, isAlex):
            if j < i: return 0
            elif i == j: return piles[i] if isAlex else -piles[i]
            if isAlex:
                return max(piles[i]+dfs(i+1, j, not isAlex), piles[j]+dfs(i, j-1, not isAlex))
            else:
                return min(-piles[i]+dfs(i+1, j, not isAlex), -piles[j]+dfs(i, j-1, not isAlex))
        
        if not piles: return False
        n = len(piles)
        
        return dfs(0, n-1, True) > 0


from functools import lru_cache

class Solution:
    def stoneGame(self, piles: List[int]) -> bool:
        N = len(piles)
        @lru_cache(None)
        def dp(i, j):
            if i > j: return 0
            if (j - i - N) % 2 == 0:
                return max(piles[i] + dp(i + 1, j), piles[j] + dp(i, j - 1))
            else:
                return max(-piles[i] + dp(i + 1, j), -piles[j] + dp(i, j - 1))
        return dp(0, N - 1) > 0
            


class Solution:
    def stoneGame(self, piles: List[int]) -> bool:
        lp = len(piles)
        
        from functools import lru_cache
        
        @lru_cache(None)
        def dp(i, j):
            if i > j: return 0
            parity = (j-i) % 2
            if parity == 1:
                return max(piles[i] + dp(i+1, j), piles[j]+dp(i, j-1))
            if parity == 0:
                return min(-piles[i] + dp(i+1, j), -piles[j]+dp(i, j-1))
            
        return dp(0, lp-1)>0

class Solution:
    def stoneGame(self, piles: List[int]) -> bool:
        
        @lru_cache(None)
        def play(i, j, alexTurn):
            if i > j:
                return 0
            
            if alexTurn:
                return max(play(i + 1, j, False) + piles[i], play(i, j - 1, False) + piles[j])
            else:
                return min(play(i + 1, j, True) - piles[i], play(i, j - 1, True) - piles[j])
            
            
        return play(0, len(piles) - 1, True) > 0

from functools import lru_cache

class Solution:

    def stoneGame(self, piles: List[int]) -> bool:
        N = len(piles)
        
        @lru_cache(None)
        def dp(i, j):
            if i > j:
                return 0
            parity = (j - i - N) % 2
            
            if parity == 1:
                return max(piles[i] + dp(i + 1, j), piles[j] + dp(i, j - 1))
            else:
                return min(-piles[i] + dp(i + 1, j), -piles[j] + dp(i, j - 1))
        
        return dp(0, N - 1) > 0


from functools import lru_cache

class Solution:
    def stoneGame(self, piles: List[int]) -> bool:
        N = len(piles)
        @lru_cache(None)
        def dp(i, j):
            # The value of the game [piles[i], piles[i+1], ..., piles[j]].
            if i > j: return 0
            parity = (j - i - N) % 2
            if parity == 1:  # first player
                return max(piles[i] + dp(i+1,j), piles[j] + dp(i,j-1))
            else:
                return min(-piles[i] + dp(i+1,j), -piles[j] + dp(i,j-1))

        return dp(0, N - 1) > 0

class Solution:
    def stoneGame(self, piles: List[int]) -> bool:
        n = len(piles)
        dp_a = [[0] * n for _ in range(n)]
        dp_b = [[0] * n for _ in range(n)]
        total = 0
        for i in range(n): 
            dp_a[i][i] = piles[i]
            total += piles[i]
        for l in range(1, n): 
            for i in range(0, n - l): 
                dp_a[i][i+l] = max(piles[i] + dp_b[i+1][i+l], piles[i+l] + dp_b[i][i+l-1]) 
                dp_b[i][i+l] = max(dp_a[i+1][i+l], dp_a[i][i+l-1])
        return dp_a[0][n-1] > total // 2


import functools

class Solution:
    def stoneGame(self, piles: List[int]) -> bool:
        n: int = len(piles)
        @functools.lru_cache(maxsize = None)
        def dp(i: int, j: int) -> int:
            if i > j:
                return 0
            parity: int = (j - i - n) % 2
            if parity == 1:
                return max(dp(i + 1, j) + piles[i], dp(i, j - 1) + piles[j])
            else:
                return min(dp(i + 1, j) - piles[i], dp(i, j - 1) - piles[j])
        return dp(0, n - 1) > 0

class Solution:
    def stoneGame(self, piles: List[int]) -> bool:
        N = len(piles)
        
        # i refers to left pointer, j refers to right pointer to piles array
        @lru_cache(None)
        def dp(i, j):
            if i > j:
                return 0
            
            parity = (j - i) % 2
            if parity == 1:
                return max(piles[i] + dp(i+1, j), piles[j] + dp(i, j-1))
            else:
                return min(-piles[i] + dp(i+1, j), -piles[j] + dp(i,j-1))
        
        return dp(0, N-1) > 0


class Solution:
    def stoneGame(self, piles):
        N = len(piles)

        @lru_cache(None)
        def dp(i, j):
            # The value of the game [piles[i], piles[i+1], ..., piles[j]].
            if i > j: return 0
            parity = (j - i - N) % 2
            if parity == 1:  # first player
                return max(piles[i] + dp(i+1,j), piles[j] + dp(i,j-1))
            else:
                return min(-piles[i] + dp(i+1,j), -piles[j] + dp(i,j-1))

        return dp(0, N - 1) > 0
    
    


from functools import lru_cache
class Solution:
    def stoneGame(self, piles: List[int]) -> bool:
        n = len(piles)
        @lru_cache(None)
        def dp(i,j):
            if i > j:
                return 0
            player = (j-i-n) % 2
            if player == 1:
                # alex
                return max(piles[i] + dp(i+1, j), piles[j] + dp(i,j-1))
            else:
                # lee
                return min(dp(i+1,j)-piles[i], dp(i,j-1)-piles[j])
        return dp(0, n-1) > 0

class Solution:
    def stoneGame(self, piles: List[int]) -> bool:
        N = len(piles)
        @lru_cache(None)
        def dp(i, j):
            if i > j: return 0
            if (j - i - N) % 2 == 0:
                return max(piles[i] + dp(i + 1, j), piles[j] + dp(i, j - 1))
            else:
                return max(-piles[i] + dp(i + 1, j), -piles[j] + dp(i, j - 1))
        return dp(0, N - 1) > 0
            


from functools import lru_cache

class Solution(object):
    def stoneGame(self, piles):
        N = len(piles)

        @lru_cache(None)
        def dp(i, j):
            # The value of the game [piles[i], piles[i+1], ..., piles[j]].
            if i > j: return 0
            parity = (j - i - N) % 2
            if parity == 1:  # first player
                return max(piles[i] + dp(i+1,j), piles[j] + dp(i,j-1))
            else:
                return min(-piles[i] + dp(i+1,j), -piles[j] + dp(i,j-1))

        return dp(0, N - 1) > 0

class Solution:
    def stoneGame(self, p: List[int]) -> bool:
        n = len(p)
        dp = [[int(j==i) for j in range(n)] for i in range(n)]
        for d in range(1, n):
            for i in range(n - d):
                # print(i, i+d)
                dp[i][i+d] = max(p[i]-dp[i+1][i+d], p[i+d]-dp[i][i+d-1])
        return dp[0][-1] > 0

class Solution:
    def stoneGame(self, piles: List[int]) -> bool:
        n = len(piles)
        dp_a = [[0] * n for _ in range(n)]
        dp_b = [[0] * n for _ in range(n)]
        for i in range(n): 
            dp_a[i][i] = piles[i]
        for l in range(1, n): 
            for i in range(0, n - l): 
                dp_a[i][i+l] = max(piles[i] + dp_b[i+1][i+l], piles[i+l] + dp_b[i][i+l-1]) 
                dp_b[i][i+l] = max(dp_a[i+1][i+l], dp_a[i][i+l-1])
        return dp_a[0][n-1] > sum(piles) // 2


class Solution:
    def stoneGame(self, piles: List[int]) -> bool:
        n = len(piles)
        #1 + (N - 1)
        @lru_cache(None)
        def solve(i, j):
            if i > j:
                return 0
            if (i + j) %2 == 1:
                return max(solve(i+1, j)+piles[i], solve(i, j-1)+piles[j])
            else:
                return min(solve(i+1, j)+piles[i], solve(i, j-1)+piles[j])
        return solve(0, n-1) > 0
        



class Solution:
    def stoneGame(self, piles):
      def dfs(left, right):
        if left > right:
          return 0
        
        if left + 1 == right:
          return piles[left]

        if dp[left][right] != None:
          return dp[left][right]

        dp[left][right] = max(
          piles[left] + dfs(left + 1, right - 1),
          piles[left] + dfs(left + 2, right),
          piles[right] + dfs(left + 1, right - 1),
          piles[right] + dfs(left, right - 2)
        )

        return dp[left][right] 

      n = len(piles)
      dp = [[None for i in range(n)] for j in range(n)]

      ALEX = dfs(0, n - 1)
      LEE = sum(piles) - ALEX
      return ALEX >= LEE


class Solution:
    def stoneGame(self, piles: List[int]) -> bool:
        prefix = [0]
        for p in piles:
            prefix.append(prefix[-1] + p)
        @lru_cache(None)
        def dp(i, j):
            if i == j:
                return piles[i]
            a = piles[i] + prefix[j + 1] - prefix[i + 1] - dp(i + 1, j)
            b = piles[j] + prefix[j] - prefix[i] - dp(i, j - 1)
            return max(a, b)
        return dp(0, len(piles) - 1) > prefix[-1] // 2

class Solution:
    def stoneGame(self, piles: List[int]) -> bool:
        
        @lru_cache(None)
        def helper(start=0, end=len(piles)):
            if end - start == 2:
                return (max(piles), min(piles))

            leeL, alexL = helper(start+1, end)
            alexL += piles[start]
            
            leeR, alexR = helper(start, end-1)
            alexR += piles[end-1]
            
            return (alexR, leeR) if alexR > alexL else (alexL, leeL)
        
        alex, lee = helper()
        return alex > lee
            


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

        dp=[[2500001]*(n+1) for _ in range(n+1)]   
        def kmp(i,j):
            if i>j:
                return 0 
            elif dp[i][j]!=2500001:
                return dp[i][j]
            else:

                
                parity=(j-i+1)%2              
                if parity==1:                                       
                    dp[i][j]=min(-piles[i]+kmp(i+1,j),-piles[j]+kmp(i,j-1)) 
                    return dp[i][j]
                else:
                    dp[i][j]=max(piles[i]+kmp(i+1,j),piles[j]+kmp(i,j-1))
                    return dp[i][j]
        return kmp(0,n-1)>0

class Solution:
    def stoneGame(self, piles: List[int]) -> bool:
        '''
        def helper(piles,i,j):
            if i==j:
                return piles[i]
            elif i+1==j:
                return max(piles[i],piles[j])
            return max(piles[i]+min(helper(piles,i+2,j),helper(piles,i+1,j-1)), piles[j]+
            min(helper(piles,i+1,j-1),helper(piles,i,j-2)))
        summ=helper(piles,0,len(piles)-1)
        #print(summ)
        if summ>sum(piles)-summ:
            return True
        return False
        '''
        n=len(piles)
        dp=[[0]*n for i in range(n)]
        #for i in range(len(piles)):
            #dp[i][i]=piles[i]
        
        for d in range(1, n): #diff between i and j is d
            for i in range(n - d):# when diff is 1, diagonally loop runs for n-1 time
                #when diff is 0, it runs for n times, ex 3X3 matrix diagonal
                j=i+d # as the diff b/w i and j is d
                if i+1==j:
                    dp[i][j] = max(piles[i],piles[j])
                else:
                    dp[i][j] = max(piles[i] + min(dp[i+2][j],dp[i+1][j-1]), piles[j] +                            min(dp[i+1][j-1],dp[i][j-2]))
        #print(dp[0][n-1])  
        return dp[0][n-1] > sum(piles) - dp[0][n-1]
        
        
        
                


from functools import lru_cache
class Solution:
    def stoneGame(self, piles: List[int]) -> bool:
        N = len(piles)
        
        @lru_cache(None)
        def dp(i,j):
            if i > j:
                return 0
            parity = (N - (j-i+1)) % 2 #0-alex, 1-lee
            # parity = (j-i-N) % 2
            if parity == 0 :
                return max(piles[i] + dp(i+1,j), piles[j]+dp(i,j-1))
            else:
                return min(-piles[i] + dp(i+1,j), -piles[j] + dp(i,j-1))
            
        return dp(0, N-1) > 0

class Solution:
    def stoneGame(self, piles: List[int]) -> bool:
        def pmin(i, j):
            if (i,j) in mincache: return mincache[(i,j)]
            if i == j: return 0
            mincache[(i,j)] =  min(pmax(i+1, j), pmax(i, j-1))
            return mincache[(i,j)]

        def pmax(i, j):
            if (i,j) in maxcache: return maxcache[(i,j)]
            if i == j: return piles[i]
            maxcache[(i,j)] =  max(piles[i] + pmin(i+1, j), pmin(i, j-1) + piles[j])
            return maxcache[(i,j)]

        mincache, maxcache = {}, {}
        p1 = pmax(0, len(piles)-1)
        p2 = sum(piles) - p1
        return p1 > p2

class Solution:
    def stoneGame(self, nums: List[int]) -> bool:
        n = len(nums)
        if n <= 2 :
            return True
        dp = [[0]*n for i in range(n)]
        
        for i in range(n):
            dp[i][i] = nums[i]
        for i in range(n-1):
            dp[i][i+1] = max(nums[i],nums[i+1])
            
        for j in range(2,n):
            for i in range(n-j):
                dp[i][j+i] = max(nums[i]+min(dp[i+1][j+i-1],dp[i+2][j+i]), nums[j+i] + min(dp[i][j+i-2],dp[i+1][j+i-1]))
        #print(dp)
        if sum(nums) - dp[0][n-1] > dp[0][n-1]:
            return False
        return True

from functools import lru_cache
class Solution:
    def stoneGame(self, piles: List[int]) -> bool:
        A = piles
        @lru_cache(maxsize=None)
        def hello(st,end,turn):
            if st > end:
                return 0
            if turn%2 == 0:
                return max(A[st]+hello(st+1,end,turn+1),A[end]+hello(st,end-1,turn+1))
            else:
                return min(hello(st+1,end,turn+1)-A[st],hello(st,end-1,turn+1)-A[end])
        t = hello(0,len(A)-1,0)
        return t > 0

class Solution:
    def stoneGame(self, piles: List[int]) -> bool:
        def solve(i,j,arr,dp):
            if i>j:
                return 0
            if dp[i][j]!=-1:
                return dp[i][j]
            
            op1 = arr[i]+solve(i+1,j,arr,dp)
            op2 = arr[j]+solve(i,j-1,arr,dp)
            dp[i][j] = max(op1,op2)
            return dp[i][j]
        dp = [[-1]*500]*500
        ans = solve(0,len(piles)-1,piles,dp)
        ans2 = sum(piles)-ans
        return ans>ans2


class Solution:
    def stoneGame(self, piles: List[int]) -> bool:
        @lru_cache(None)
        def dp(i, j):
            if i >= j or j >= len(piles): return 0
            if i + 1 == j:
                return max(piles[i:j + 1])
            res = piles[i] + max(dp(i + 2, j), dp(i + 1, j - 1))
            res = max(res, piles[j] + max(dp(i, j - 2), dp(i + 1, j - 1)))
            return res
        return dp(0, len(piles) - 1) > sum(piles)//2


class Solution:
    # @lru_cache(None)
    def stoneGame(self, piles: List[int]) -> bool:
        result = dict()
        
        def Alex(start, end) -> int:
            if start == end:
                return piles[start]
            if (start, end) in result:
                return result[(start, end)]
            else:
                result[(start, end)] = max(Lee(start + 1, end) + piles[start], Lee(start, end - 1) + piles[end])
            return result[(start, end)]
            
        def Lee(start, end) -> int:
            if start == end:
                return 0
            if (start, end) in result:
                return result[(start, end)]
            else:
                result[(start, end)] =  min(Alex(start + 1, end), Alex(start, end - 1))
            return result[(start, end)]
        Alex(0, len(piles) - 1)
        summ = sum(piles)
        # print(result[(0, len(piles - 1))])
        # print(summ)
        return result[(0, len(piles) - 1)] > (summ - result[(0, len(piles) - 1)])

class Solution:
    def stoneGame(self, piles: List[int]) -> bool:
#         alex = [[0 for x in range(2)] for y in range((len(piles)//2)+1)]
#         lee = [[0 for x in range(2)] for y in range((len(piles)//2)+1)]
#         first,last = 0,len(piles)-1
#         turn = 0
#         x,y = 1,1
#         while first < last:
#             if turn == 0:
#                 alex[x][0] = max(alex[x-1][0],alex[x-1][1]) + first
#                 alex[x][1] = max(alex[x-1][0],alex[x-1][1]) + last
            
        dp = [[-1 for x in range(len(piles))] for y in range(len(piles))]
        def recur_dp(si,ei,turn):
            if si > ei:
                return 0
            if dp[si][ei] != -1:
                return dp[si][ei]
            if turn == 0: #alex turn
                start = recur_dp(si+1,ei,1 - turn) + piles[si]
                end = recur_dp(si,ei-1,1-turn) + piles[ei]
                dp[si][ei] = max(start,end)
                return dp[si][ei]
            else:
                start = recur_dp(si+1,ei,1-turn) - piles[si]
                end = recur_dp(si,ei-1,1-turn) - piles[ei]
                dp[si][ei] = min(start,end)
                return dp[si][ei]
        recur_dp(0,len(piles)-1,0)
        return dp[0][len(piles)-1] >= 0
            
        


class Solution:
    def stoneGame(self, piles: List[int]) -> bool:
        presum = [0]
        for pile in piles:
            presum.append(presum[-1]+pile)
        
        @lru_cache(None)
        def solve(a,b):
            if a==b:
                return piles[a]
            return max(presum[b+1]-presum[a]-solve(a+1,b), presum[b+1]-presum[a]-solve(a,b-1))
        gain = solve(0,len(piles)-1)
        return gain>presum[-1]-gain


from functools import lru_cache

class Solution:
    def stoneGame(self, piles: List[int]) -> bool:
        # alex's best score must be greater than total score // 2
        totalScore = sum(piles)
        memo = {}
        
        @lru_cache(None)
        def helper(first = 0, last = len(piles) - 1, ):
            if first > last:
                return 0
            isAlex = (last - first - len(piles)) % 2 
            # total score from this state of the game minus ( - ) min of my opponent's score
            if isAlex:
                return max(piles[first] + helper(first + 1, last), piles[last] + helper(first, last - 1))
            else:
                return min(-piles[first] + helper(first + 1, last), -piles[last] + helper(first, last - 1))
            # memo[qstring] = myMaxScore
            # return myMaxScore
        
        return helper() > 0

class Solution:
    def stoneGame(self, piles: List[int]) -> bool:
        l = len(piles)
        if l == 0:
            return False
        dp = [[0 for i in range(l)] for j in range(l)]
        
        for i in range(l):
            dp[i][i] = piles[i]
            
        for i in range(1,l):
            for j in range(l-i):
                dp[j][i+j] = max(piles[j]-dp[i+j][j], piles[i+j]-dp[i+j][i+j-1])
        return dp[0][l-1] > 0

class Solution:
    def stoneGame(self, piles: List[int]) -> bool:
        
        # returns the maximum points Alex can get
        mem = {}
        def dp(l, r):
            if l > r:
                return 0
            if (l, r) in mem:
                return mem[(l, r)]
            alex_turn = ((r - l) % 2 == 1)
            reward_left = dp(l+1, r)
            reward_right = dp(l, r-1)
            if alex_turn:
                res = max(reward_left + piles[l], reward_right + piles[r])
            else:
                res = min(reward_left, reward_right)
            mem[(l, r)] = res
            return res
        
        reward = dp(0, len(piles)-1)
        total = sum(piles)
        return reward > total / 2


class Solution:
    def stoneGame(self, piles: List[int]) -> bool:
        total = sum(piles)
        pre_sums = [0] * (len(piles) + 1)
        
        for i in range(len(piles)):
            pre_sums[i+1] = piles[i] + pre_sums[i]
        
        m = {}
        def dfs(start, end):
            if end == start:
                return piles[end]
            if (start, end) in m:
                return m[(start, end)]
            interval_total = pre_sums[end+1] - pre_sums[start]
            max_stone = interval_total - min(dfs(start+1, end), dfs(start, end-1))

            m[(start, end)] = max_stone
            
            return max_stone
        
        Alex_score = dfs(0, len(piles)-1)
        if Alex_score > total//2:
            return True
        else:
            return False

class Solution:
    def stoneGame(self, piles: List[int]) -> bool:
        memo = {}
        
        Alex = self.firstscore(0, len(piles), memo, piles)
        Lee = sum(piles) - Alex
        return Alex > Lee
    
    def firstscore(self, i, j, memo, piles):
        if i >= j:
            return 0
        if (i, j) in memo:
            return memo[(i, j)]
        res = max(
            piles[i] + min(
                            self.firstscore(i+2, j, memo, piles),
                            self.firstscore(i+1, j-1, memo, piles)
                          ),
            piles[j-1] + min(
                            self.firstscore(i, j-2, memo, piles),
                            self.firstscore(i+1, j-1, memo, piles)
                          )
                  )
        
        memo[(i, j)] = res
        return res

class Solution:
    def __init__(self):
        self.g=[]        
    def recurse(self, piles, i, j): 
        if self.g[i][j]:
            return self.g[i][j]
        if j - i <= 1:
            return True
        self.g[i][j] = self.recurse(piles, i+1, j) or self.recurse(piles, i, j-1)
        return self.g[i][j]
    
    def stoneGame(self, piles: List[int]) -> bool:
        if not piles: 
            return True
        self.g = [[False]*len(piles) for i in range(len(piles))]
        ans= self.recurse(piles, 0, len(piles)-1)
        return ans

class Solution:
    def stoneGame(self, piles: List[int]) -> bool:
        dp=[[-1 for i in range(len(piles))] for j in range(len(piles))]
        left = 0
        right = len(piles)-1
        out = self.helper(piles,left,right,dp,0)
        if(out>sum(piles)-out):
            return True
        return False
        
    def helper(self,piles,left,right,dp,flag):
        if(left>right):
            return 0
        
        if(dp[left][right]!=-1):
            return dp[left][right]
        
        if(flag==0):
            one = self.helper(piles,left+1,right,dp,1)+piles[left]
            two = self.helper(piles,left,right-1,dp,1)+piles[right]
            dp[left][right] = max(one,two)
            return max(one,two)
        
        else:
            one = self.helper(piles,left+1,right,dp,0)
            two = self.helper(piles,left,right-1,dp,0)
            dp[left][right] = min(one,two)
            return min(one,two)


class Solution:
    def stoneGame(self, piles: List[int]) -> bool:
        
        self._visited = {}
        alex_minus_lee = self.search(piles, 0, len(piles) - 1)
        return alex_minus_lee > 0
        
    
    def search(self, piles: List[int], start: int, end: int):
        if start > end:
            return 0
        key = (start, end)
        if key in self._visited:
            return self._visited[key]
        
        score = max(piles[start] - self.search(piles, start + 1, end), 
                    piles[end] - self.search(piles, start, end - 1))
        
        self._visited[key] = score
        
        return score
        
        
        


class Solution:
    def stoneGame(self, piles: List[int]) -> bool:
        memo = {}
        
        def dfs(i, j, alex):
            if (i, j, alex) in memo:
                return memo[i, j, alex]
            
            if i >= j:
                return 0
            
            left = dfs(i+1, j, not alex)
            right = dfs(i, j - 1, not alex)
            
            if not alex:
                ans = min(left, right)
            else:
                ans = max(left + piles[i], right + piles[j])
            
            memo[i, j, alex] = ans
            return ans
        
        a = dfs(0, len(piles) - 1, True)
        return a > sum(piles) / 2        

class Solution:
    def stoneGame(self, piles: List[int]) -> bool:
        n = len(piles)
        memo = [[-sys.maxsize for i in range(n)] for j in range(n)]
        
        def DFS(left:int,right:int)->int:
            if memo[left][right]!=-sys.maxsize:
                return memo[left][right]
            if left>=right:
                return 0
            score = max(piles[left]-DFS(left+1,right),piles[right]-DFS(left,right-1))
            memo[left][right] = score
            return score
        
        
        return True if DFS(0,n-1)>0 else False

class Solution:
    def stoneGame(self, piles: List[int]) -> bool:
        l = len(piles)
        
        dp = [[[0,0] for _ in range(l+1)] for _ in range(l+1)]
        
        for i in range(1, l+1):
            dp[i][i][0] = piles[i-1]
            
        for i in range(l+1,-1,-1):
            for j in range(i+1, l+1):
                left = piles[i-1] + dp[i+1][j][1]
                right = piles[j-1] + dp[i][j-1][1]
                if left > right:
                    dp[i][j][0] = left
                    dp[i][j][1] = dp[i+1][j][0]
                else:
                    dp[i][j][0] = right
                    dp[i][j][1] = dp[i][j-1][0]
                    
        return dp[1][l][0] > dp[1][l][1]

class Solution:
    def stoneGame(self, piles: List[int]) -> bool:
        
        def pmin(i, j):
            if (i, j) in mincache:
                return mincache[(i, j)]
            elif i == j:
                return piles[i]
            mincache[(i, j)] = min(pmax(i+1, j), pmax(i, j-1))
            return mincache[(i, j)]
        
        def pmax(i, j):
            if (i, j) in maxcache:
                return maxcache[(i, j)]
            elif i == j:
                return piles[i]
            maxcache[(i, j)] = max(piles[i] + pmin(i+1, j),
                                   piles[j] + pmin(i, j-1))
            return maxcache[(i, j)]
        
        mincache, maxcache = {}, {}
        p1 = pmax(0, len(piles)-1)
        p2 = sum(piles) - p1
        return p1 > p2

def memoize(f):
    memo = {}
    def inner(*args):
        tup = tuple(args)
        if tup in memo:
            return memo[tup]
        res = f(*args)
        memo[tup] = res
        return res
    return inner
        
class Solution:
    def stoneGame(self, piles: List[int]) -> bool:
        memo = {}
        def score(i=0, j=len(piles)-1):
            if i == j: 
                return piles[i]
            if (i,j) in memo: return memo[(i,j)]
            lscore = piles[j] - score(i, j-1)
            rscore = piles[i] - score(i+1, j)
            result = max(lscore, rscore)
            memo[(i,j)] = result
            return result
        return score() > 0


class Solution:
    def stoneGame(self, piles: List[int]) -> bool:
        if not piles:
            return False
        
        cache = {}
        
        def dfs(l, r):
            # Calculate the best sum of Alex.
            if l >= r + 1:
                return 0
            if (l, r) in cache:
                return cache[(l, r)]
            res = max(piles[l] + min(dfs(l+2, r), dfs(l+1, r-1)), piles[r] + min(dfs(l, r-2), dfs(l+1, r-1)))   
            cache[(l, r)] = res
            return cache[(l, r)]
        
        
        sum_a = dfs(0, len(piles) - 1)
        sum_b = sum(piles) - sum_a
        # print(sum_a)
        return sum_a > sum_b

class Solution:
    def stoneGame(self, piles: List[int]) -> bool:
        dp = {}
        
        def helper(i, j):
            if i == j:
                return piles[i]
            if (i, j) in dp:
                return dp[(i, j)] 
            
            dp[(i, j)] = max(piles[i]+helper(i+1, j), piles[j]+helper(i, j-1))
            return dp[(i , j)]

        
        if helper(0, len(piles)-1) > sum(piles)//2:
            return True
        return False
            
            


class Solution:
    def stoneGame(self, piles: List[int]) -> bool:
        dp = {}
        
        def backtracking(i, j):
            if i == j:
                return piles[i]
            if not (i + 1, j) in dp:
                dp[(i + 1, j)] = backtracking(i + 1, j)
            res = piles[i] - dp[(i + 1, j)]
            if not (i, j - 1) in dp:
                dp[(i, j - 1)] = backtracking(i, j - 1)
            res = max(res, piles[j] - dp[i, j - 1])
            return res
        
        return backtracking(0, len(piles) - 1) > 0

class Solution:
    def stoneGame(self, piles: List[int]) -> bool:
        dp = {}
        
        def backtracking(i, j):
            if i == j:
                return piles[i]
            if not (i, j) in dp:
                dp[(i, j)] = max(piles[i] - backtracking(i + 1, j), piles[j] - backtracking(i, j - 1))
            return dp[(i, j)]
        
        return backtracking(0, len(piles) - 1) > 0

class Solution:
    def stoneGame(self, piles: List[int]) -> bool:
        ''' Use Math one-liner: return True
        Solution 1. Dynamic Programming:'''
        n = len(piles)
        @lru_cache(None)
        def dp(i, j):
            if i > j:
                return 0
            parity = (j - i - n) % 2
            if parity == 1: # first player
                return max(piles[i] + dp(i+1, j), piles[j] + dp(i, j-1))
            else:
                return min(-piles[i] + dp(i+1, j), -piles[j] + dp(i, j-1))
        return dp(0, n-1) > 0

class Solution:
    def stoneGame(self, piles: List[int]) -> bool:
        '''
        def optimalMax(piles: List[int]):
            if len(piles)==1:
                return piles[0]
            return max(piles[0]+sum(piles[1:])-optimalMax(piles[1:]),
                   piles[-1]+sum(piles[:-1])-optimalMax(piles[:-1]))
        return optimalMax(piles)>sum(piles)/2
        '''
        # actual list: piles[i:j]
        def optimalMax(piles: List[int], dpTable, i,j,sum_):
            if j-i==1:
                dpTable[i][j-1]=piles[i]
                return piles[i]
            if dpTable[i][j-1]<=0:
                dpTable[i][j-1]=max(sum_-optimalMax(piles,dpTable,i+1,j,sum_-piles[i]),
                   sum_-optimalMax(piles,dpTable,i,j-1,sum_-piles[j-1]))
            return dpTable[i][j-1]
        dpTable=[[0 for _ in piles] for _ in piles]
        #print(dpTable)
        return optimalMax(piles, dpTable,0,len(piles),sum(piles))>sum(piles)/2
    
    


class Solution:
    def stoneGame(self, piles: List[int]) -> bool:
        n = len(piles)
        presum = [0] * (n + 1)
        for i in range(1, n + 1):
            presum[i] = presum[i - 1] + piles[i - 1]
        self.dp = [[0 for j in range(n)] for i in range(n)]
        ans = self.solve(piles, 0, n - 1, presum)
        return ans > ans - presum[n]
        
    def solve(self, piles, i, j, presum):
        if self.dp[i][j] > 0:
            return self.dp[i][j]

        if i == j:
            return piles[i]
        
        result = piles[i] + presum[j] - presum[i] - self.solve(piles, i + 1, j, presum)
        result = max(result, piles[j] + presum[j - 1] - presum[i - 1] - self.solve(piles, i, j - 1, presum))
        self.dp[i][j] = result
        return result

from functools import lru_cache
class Solution:
    def stoneGame(self, piles: List[int]) -> bool:
        n = len(piles)
        @lru_cache(None)
        def dp(i,j):
            if i > j:
                return 0
            player = (j-i-n) % 2
            if player == 1:
                # alex
                return max(piles[i] + dp(i+1, j), piles[j] + dp(i,j-1))
            else:
                # lee: he requires to decrease alex's score, so we need to find the minimum
                return min(dp(i+1,j)-piles[i], dp(i,j-1)-piles[j])
        return dp(0, n-1) > 0

class Solution:
    def stoneGame(self, piles: List[int]) -> bool:
        alex = 0
        lee = 0
        
        alex_turn = True
        
        while len(piles) != 0:
            maxi = (-1,0)
            for i in range(len(piles)):
                if piles[i] > maxi[0]:
                    maxi = (piles[i], i)

            piles.pop(maxi[1])
            if alex_turn:
                alex += maxi[0]
                alex_turn = False
            else:
                lee += maxi[0]
                alex_turn = True
        
        if alex > lee:
            return True
        return False

class Solution:
    memo = []

    def stoneGame(self, piles: List[int]) -> bool:
        length = len(piles)
        self.memo = [[[-1] * (length + 1) for _ in range(length + 1)] for i in range(2)]
        return (self.helper(0, length-1, piles, 1)) >= 0

    def helper(self, l, r, piles, ID):
        if l > r:
            return 0
        if self.memo[ID][l][r] != -1:
            return self.memo[ID][l][r]

        next = abs(ID - 1)
        if ID == 1:
            self.memo[ID][l][r] = max(piles[l] + self.helper(l + 1, r, piles, next),
                                      piles[r] + self.helper(l, r - 1, piles, next))
        else:
            self.memo[ID][l][r] = min(-piles[l] + self.helper(l + 1, r, piles, next),
                                      -piles[r] + self.helper(l, r - 1, piles, next))
        return self.memo[ID][l][r]



class Solution:
    def stoneGame(self, piles: List[int]) -> bool:
        # Other solution
        mem = dict()
        
        def search(i, j):
            if i > j:
                return 0
            
            if (i,j) in mem:
                return mem.get((i,j))
            
            side = (j-i+1) % 2
            
            if side == 0:
                ret = max(search(i+1,j)+piles[i],  search(i,j-1)+piles[j])
                mem[(i,j)] = ret
                return ret
            else:
                ret = min(search(i+1,j)-piles[i], search(i, j-1)-piles[j])
                mem[(i,j)] = ret
                return ret
            
            
            
        return search(0,len(piles)-1) > 0


class Solution:
    def stoneGame(self, piles: List[int]) -> bool:
        return self.getmax(piles, 0, 0, len(piles)-1, {}) > 0
    
    def getmax(self, piles, p, i, j, cache):
        if (i > j):
            return 0
        if (i,j,p) in cache:
            return cache[(i,j,p)]
        if p == 0:
            cache[(i,j,p)] = max(piles[i] + self.getmax(piles, 1, i+1, j, cache), piles[j] + self.getmax(piles, 1, i, j-1, cache))
        else:
            cache[(i,j,p)] = min(-piles[i] + self.getmax(piles, 0, i+1, j, cache), -piles[j] + self.getmax(piles, 0, i, j-1, cache))
        return cache[(i,j,p)]

class Solution:
    def stoneGame(self, piles: List[int]) -> bool:
        memo = {}
        def find(i,j):
            if (i,j) in memo:
                return memo[(i,j)]
            if j - i == 1:
                return max(piles[i],piles[j])
            memo[(i,j)] = max(min(find(i + 1, j-1), find(i + 2, j)) + piles[i], min(find(i + 1, j - 1), find(i, j - 2)) + piles[j])
            return memo[(i,j)]
        return find(0,len(piles) - 1) > sum(piles) // 2


class Solution:
    def stoneGame(self, piles: List[int]) -> bool:
        
        i = 0
        j = len(piles) - 1
        self.memo = {}
        score = self.recurse(piles, i, j, True)
        return score > 0
        
    
    
    def recurse(self, piles, i, j, a_turn):
        
        if (i,j) in self.memo:
            return self.memo[(i,j)]
        
        if i == j:
            return 0
        
        if a_turn:
            l = self.recurse(piles, i+1, j, False) + piles[i]
            r = self.recurse(piles, i, j-1, False) + piles[j]
            self.memo[(i,j)] = max(l, r)
        else:
            l = self.recurse(piles, i+1, j, True) - piles[i]
            r = self.recurse(piles, i, j-1, True) - piles[j]
            self.memo[(i,j)] = min(l, r)
        return self.memo[(i,j)]

from collections import defaultdict
class Solution:
    def stoneGame(self, piles: List[int]) -> bool:
        self.dp_table = defaultdict(int)
        
        def maximize_score_gap(piles,left,right):
            
            if left == right:
                return piles[left]
            
            if (left,right) in self.dp_table:
                return self.dp_table[(left,right)]
            
            choose_left = piles[left] - maximize_score_gap( piles, left+1, right)
            choose_right = piles[right] - maximize_score_gap( piles, left, right-1)
            
            self.dp_table[ (left,right) ] = max( choose_left, choose_right )
            
            return self.dp_table[(left,right)]
        
        score_gap_for_alex = maximize_score_gap( piles, left = 0, right = len(piles)-1 )
        
        return score_gap_for_alex > 0


class Solution:
    def stoneGame(self, piles: List[int]) -> bool:
        def dp(m,n,x):
            if m>n:
                return 0
            if t[m][n]!=-1:
                return t[m][n]
            else:
                if x==0:
                    self.cost1+=max((dp(m+1,n,1)+piles[m]),dp(m,n-1,1)+piles[n])
                    t[m][n]=self.cost1
                    return t[m][n]
                else:
                    self.cost2+=max((dp(m+1,n,0)+piles[m]),dp(m,n-1,0)+piles[n])
                    t[m][n]=self.cost2
                    return t[m][n]
        self.cost1=0
        n=len(piles)
        self.cost2=0
        t=[[-1]*(n+1) for  i in range(n+1)]
        dp(0,n-1,0)
        print((self.cost1,self.cost2))
        if self.cost1>self.cost2:
            return True
        else:
            return False
                


class Solution:
    def stoneGame(self, piles: List[int]) -> bool:
        dp = [[[0, 0] for _ in range(len(piles))] for _ in range(len(piles))]
        
        for i in range(len(piles)):
            dp[i][i][0] = piles[i]
            dp[i][i][1] = 0
        
        for l in range(1, len(piles)):
            for r in range(len(piles) - l):
                c = r + l
                left = piles[r] + dp[r + 1][c][1]
                right = piles[c] + dp[r][c - 1][1]
                dp[r][c][0] = max(left, right)
                
                if left > right:
                    dp[r][c][1] = dp[r + 1][c][0]
                else:
                    dp[r][c][1] = dp[r][c - 1][0]
        
        return dp[0][len(piles) - 1][0] > dp[0][len(piles) - 1][1]


import numpy as np
class Solution:
    def stoneGame(self, piles: List[int]) -> bool:
        return True

class Solution:
    def stoneGame(self, piles: List[int]) -> bool:
        prefix = list(itertools.accumulate(piles))
        
        @lru_cache(maxsize=None)
        def getScore(i, j):
            if i > j:
                return 0
            
            stones = float('-inf')
            prev = prefix[i - 1] if i - 1 >= 0 else 0
            stones = max(stones, prefix[j] - prev - getScore(i + 1, j))
            stones = max(stones, prefix[j] - prev - getScore(i, j - 1))
            return stones
            
        alex_score = getScore(0, len(piles) - 1)
        if alex_score > prefix[-1] - alex_score:
            return True
        return False

class Solution:
    
    def stoneGame(self, piles):
        
        n = len(piles)
        memo = dict()
        
        def dp(i,j):
            if i>j: return 0
            if (i,j) in memo: return memo[(i,j)]
            
            ans = max(piles[i] - dp(i+1, j), piles[j] - dp(i, j-1))
            memo[(i,j)] = ans
            return ans
        return dp(0, n-1) > 0
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
    
    def stoneGame1(self, piles):
        # three methods, dp, memo+recursive
        n = len(piles)
        
        memo = dict()
        def dp(i,j):
            if i>j: return 0
            if (i,j) in memo: return memo[(i,j)]
            
            if (j-i+n) % 2 == 1: # player 1
                ans = max(piles[i] + dp(i+1,j), piles[j] + dp(i,j-1))
            else:
                ans = min(-piles[i] + dp(i+1, j), -piles[j] + dp(i,j-1))
            memo[(i,j)] = ans
            return ans
        return dp(0, n-1) > 0 # 相对分数
    
    def stoneGame2(self, piles):
        n = len(piles)
        dp = [[0]*n for _ in range(n)]
        for i in range(n):
            dp[i][i] = piles[i]
        for alen in range(2, n+1):
            for i in range(0, n-alen+1): # when i=n-alen, alen=n
                j = i+alen-1 # j - i + 1 = alen, so j = i-1+alen
                dp[i][j] = max(piles[i] - dp[i+1][j], piles[j] - dp[i][j-1])
        return dp[0][n-1] > 0 # 相对分数
    
    def stoneGame3(self, piles): # 记忆化递归的方法！相对比较容易写出来
        n = len(piles)
        memo = dict()
        def dp(i,j):
            if i>j: return 0
            if (i,j) in memo: return memo[(i,j)]
            
            ans = max(piles[i] - dp(i+1,j), piles[j] - dp(i, j-1)) # min-max过程
            memo[(i,j)] = ans
            return ans
        return dp(0,n-1)>0 # 相对分数，也就是 score(alex) - score(lee)
    
    def stoneGame4(self, piles):
        return True
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
    
    def stoneGame3(self, piles):
        n = len(piles)
        # dp[i] = max(your stones - op_stones) for piles[i] to piles[i+alen-1] i+alen-1-i+1 = alen = length of piles
        dp = [0] * n
        for alen in range(2, n+1):
            for i in range(0, n-alen+1):
                dp[i] = max(piles[i] - dp[i+1], piles[i+alen-1] - dp[i]) # 问题，二维转一维的技巧是什么？
        return dp[0] > 0
    
    
    def stoneGame2(self, piles):
        # dp[i][j] = max(yourscore - op_stones) for piles[i] ~ piles[j]
        n = len(piles)
        dp = [[0] * n for _ in range(n)]
        for i in range(n):
            dp[i][i] = piles[i]
        
        for alen in range(2, n+1): #长度为从2到n，构造
            for i in range(0, n-alen+1): # i这个子问题的范围
                j = i + alen - 1
                dp[i][j] = max(piles[i] - dp[i+1][j], piles[j] - dp[i][j-1])
                # j = i + alen - 1 代入
                # dp[i][j] = max(piles[i] - dp[i+1][j], piles[i+alen-1] - dp[i][j-1])
                # 然后直接把j去掉:
                # dp[i] = max(piles[i] - dp[i+1], piles[i+alen-1] - dp[i]) 就是1D的写法。。。
        return dp[0][n-1] > 0
        
    
    def stoneGame1(self, piles: List[int]) -> bool:
        # minmax + dp 或者记忆化递归
        # 你和对手都是选择“最佳”的option来选择
        
        # 第一种解法：minmax
        # def score(s, l, r)
        #    if l>r: return 0
        #    return max(s[l] - score(s, l+1, r), # left
        #               s[r] - score(s, l, r-1)) # right
        #    对手的最大值，自己的最小值下的 最大值
        #    return score(s, 0, n-1) > 0
        # time: O(2^n), space O(n)
        
        # 第二种解法：minmax + memorization / DP
        # dp[i][j] = best relative score of subarray s[i] ~ s[j]
        # time O(n^2), space (O^2) -> O(n)
        
        # solution 1, recursive, 不记忆中间结果，无法达到最优解！O(2^n) 记忆化递归，容易java的stack爆掉。。。
        dp = dict()
        def score(piles, l, r):
            # left, right
            if (l,r) in dp:
                return dp[(l,r)]
            if l == r:
                dp[(l,r)] = piles[l] # 只剩下一堆的话，就取它了，没有其他可以选择的了！
                return piles[l]
            res = max(piles[l] - score(piles, l+1, r), piles[r] - score(piles, l, r-1))
            # 我，当前有两种选择，拿l或者拿r，如果拿l，则得分为piles[l]，失分为对手从l+1,r的区间能得到的最大值（对手的最大值，就是我的最小值）
            # 如果拿r，则得分为piles[r]，失分为对手从l, r-1的区间能得到的最大值（对手的最大值，就是我的最小值）
            # 所以这个过程就是经典的minmax过程
            dp[(l,r)] = res
            return res
        
        res = score(piles, 0, len(piles)-1) 
        return True if res > 0 else False

class Solution:
    # return True would work because Alex always wins the game
    def stoneGame(self, piles: List[int]) -> bool:
        prefix = list(itertools.accumulate(piles))
        
        @lru_cache(maxsize=None)
        def getScore(i, j):
            if i > j:
                return 0
            
            stones = float('-inf')
            prev = prefix[i - 1] if i - 1 >= 0 else 0
            stones = max(stones, prefix[j] - prev - getScore(i + 1, j))
            stones = max(stones, prefix[j] - prev - getScore(i, j - 1))
            return stones
            
        alex_score = getScore(0, len(piles) - 1)
        if alex_score > prefix[-1] - alex_score:
            return True
        return False

class Solution:
    
    def stoneGame(self, piles: List[int]) -> bool:
        
        self.piles = piles
        self.dp = {}
        
        def helper(i, j, turn=True):
            
            if i > j:
                return 0
            if (i,j) in self.dp:
                return self.dp[(i,j)]
            alex = 0
            if turn:
                alex = max(self.piles[i] + helper(i+1, j, turn=False), self.piles[j] + helper(i, j-1, turn=False))
            else:
                alex = max(helper(i+1, j, turn=True), helper(i, j-1, turn=True))
            
            self.dp[(i,j)] = alex
            return self.dp[(i,j)]
                
        
        alex = helper(0,len(self.piles)-1)
        return 2*alex > sum(self.piles)

class Solution:
    def stoneGame(self, piles: List[int]) -> bool:
        memo = {}
        def subseq(i, j):
            if (i,j) in memo:
                return memo[(i,j)]
            if i > j:
                return 0
            if (j - i - len(piles)) % 2:
                memo[(i,j)] = max(piles[i] + subseq(i+1, j), piles[j] + subseq(i, j-1))
            else:
                memo[(i,j)] = min(-piles[i] + subseq(i+1, j), -piles[j] + subseq(i, j-1))
            return memo[(i,j)]
        return subseq(0, len(piles)-1) > 0

class Solution:
    def stoneGame(self, piles: List[int]) -> bool:
        dp = {}
        def inner(i,j, chance):
            if i == j and chance:
                return piles[i]
            if i > j:
                return 0
            if dp.get((i,j,chance)) == None:
                if chance:
                    dp[(i,j,chance)] = max(piles[i]+inner(i+1,j, False), piles[j]+inner(i,j-1, False))
                else:
                    dp[(i,j,chance)] = max(inner(i+1,j, True), inner(i,j-1, True))
            return dp[(i,j,chance)]
        a = inner(0,len(piles)-1, True)
        return True if a > (sum(piles)-a) else False


from collections import defaultdict

def maxsum(piles,left,right,memo):
    if memo[left,right]:
        return memo[left,right]
    
    if left==right:
        return piles[left],0
    
    y1,x1 = maxsum(piles,left+1,right,memo)
    y2,x2 = maxsum(piles,left,right-1,memo)
    
    if x1+piles[left]<x2+piles[right]:
        memo[left,right]=x2+piles[right],y2
    else:
        memo[left,right]=x1+piles[left],y1
    
    return memo[left,right]
    
    

class Solution:
    def stoneGame(self, piles: List[int]) -> bool:
        memo = defaultdict(int)
        
        x,y = maxsum(piles,0,len(piles)-1,memo)
        
        return True if x>y else False

from collections import defaultdict

class Solution:
    def stoneGame(self, piles: List[int]) -> bool:
        
        self.dp_table = defaultdict( int )
        
        def maximize_score_gap( piles, left, right):
            
            if left == right:
                # Base case
                # only one pile of stone remains
                return piles[left]
            
            if (left, right) in self.dp_table:
                # Directly return if this case has been computed before
                return self.dp_table[ (left, right)] 
            
            # Use optimal substructure to compute maximized score gap
            choose_left = piles[left] - maximize_score_gap( piles, left+1, right)
            choose_right = piles[right] - maximize_score_gap( piles, left, right-1)
            
            # update DP table
            self.dp_table[ (left,right) ] = max( choose_left, choose_right )
            
            return self.dp_table[ (left,right) ]
        
        # ------------------------------------------------
        
        score_gap_for_alex = maximize_score_gap( piles, left = 0, right = len(piles)-1 )
        
        return score_gap_for_alex > 0

class Solution:
    def stoneGame(self, piles):
        cache = {}
        piles = tuple(piles)
        
    
        res = [0]
        for k in range(len(piles)):
            res.append(res[-1] + piles[k])
        
        
        def firstscore(i,j):
            if i>=j: return 0
            if j==i+1 and j < len(piles): return piles[i]
            if (i,j) in cache: return cache[i,j]
            r = max(res[j] - res[i] - firstscore(i + 1, j), res[j] - res[i] - firstscore(i, j - 1))
            cache[i,j] = r
            return r

        Alex = firstscore(0,len(piles))
        Lee = sum(piles) - Alex
        return Alex > Lee

class Solution:
    def stoneGame(self, piles: List[int]) -> bool:
        N = len(piles) // 2
        dp1 = [0] * (N + 1)
        dp2 = [0] * (N + 1)
        
        rot = 0
        temp = piles.copy()
        
        i = 1
        while len(temp) > 0:
            alex = max(temp[0], temp[-1])
            if temp[0] == temp[-1]:
                rot += 1
            if alex == temp[0]:
                dp1[i] = dp1[i - 1] + temp[0]
                temp.pop(0)
            else:
                dp1[i] = dp1[i - 1] + temp[-1]
                temp.pop()
            print(alex)
            print(temp)
            lee = max(temp[0], temp[-1])
            if temp[0] == temp[-1]:
                rot += 1
                
            if lee == temp[0]:
                dp2[i] = dp2[i - 1] + temp[0]
                temp.pop(0)
            else:
                dp2[i] = dp2[i - 1] + temp[-1]
                temp.pop()
            print(lee)
            print(temp)
            i += 1
        print(dp1)
        print(dp2)
        
        if rot > 0:
            return True
        return dp1[-1] > dp2[-1]


class Solution:
    def stoneGame(self, piles: List[int]) -> bool:
        sums = [0] + list(itertools.accumulate(piles))
        def get_sum(i, j):
            return sums[j+1] - sums[i]
        
        n = len(piles)
        dp = [[-1]*n for _ in range(n)]
        def solve(i, j):
            if i > j:
                return 0
            if i == j:
                return piles[i]
            if dp[i][j] >= 0:
                return dp[i][j]
            sa = piles[i] + get_sum(i+1, j) - solve(i+1, j)
            sb = piles[j] + get_sum(i, j-1) - solve(i, j-1)
            dp[i][j] = max(sa, sb)
            return dp[i][j]
        alice = solve(0, len(piles)-1)
        return alice > get_sum(0, n-1) - alice


class Solution:
    def stoneGame(self, piles: List[int]) -> bool:
        
        self.memo = {}
        
        def dfs(l, r, isAlex, alexSum, leeSum):
            key = (l, r, isAlex)
            
            if key in self.memo:
                return self.memo[key]
            
            if l == r:
                leeSum += piles[l]
                r = (alexSum > leeSum)
                self.memo[key] = r
                return r
            
            if isAlex:
                r1 = dfs(l+1, r, False, alexSum + piles[l], leeSum)
                r2 = dfs(l, r-1, False, alexSum + piles[r], leeSum)
            else:
                r1 = dfs(l+1, r, True, alexSum, leeSum + piles[l])
                r2 = dfs(l, r-1, True, alexSum, leeSum + piles[r])
                
            self.memo[key] = r1 or r2
            return r1 or r2
        
        return dfs(0, len(piles) -1, True, 0, 0)

class Solution:
    from functools import lru_cache
    def stoneGame(self, piles: List[int]) -> bool:
        n = len(piles)
        
        @lru_cache(None)
        def dp(i, j, asum, lsum, aturn):
            
            if i > j:
                return (0, 0)
            
            if aturn:
                asum += max(piles[i] + dp(i+1, j, asum, lsum, False)[0], piles[j] + dp(i, j-1, asum, lsum, False)[0])
            else:
                lsum += max(piles[i] + dp(i+1, j, asum, lsum, True)[1], piles[j] + dp(i, j-1, asum, lsum, True)[1])
            
            return (asum, lsum)
        
        asum, lsum = dp(0, n-1, 0, 0, True)

        return bool(asum - lsum)

class Solution:
    def stoneGame(self, piles: List[int]) -> bool:
        # Other solution
        self.dic = {}
        self.length = len(piles)
        
        def search(i,j):
            if i > j:
                return 0
            
            if (i,j) in self.dic:
                return self.dic.get((i,j))
            
            parity = (j-i+1) % 2
            
            if parity == 0:
                ret1 = max(piles[i]+search(i+1,j), piles[j]+search(i,j-1))
                self.dic[(i,j)] = ret1
                return ret1
            else:
                ret2 = min(-piles[i]+search(i+1,j), -piles[j]+search(i,j-1))
                self.dic[(i,j)] = ret2
                return ret2
            
        return search(0,self.length-1) > 0


class Solution:
    def __init__(self):
        self.result=False
    
    def backtrack(self,arr,start,end,alex,lee,count,visited):
        if start>end and lee<alex:
              return 1
        elif start>end:
            return 0
        elif visited[start][end]!=-1:
            return visited[start][end]
        else:
            a,b=0,0
            if count%2==0:                a=max(self.backtrack(arr,start+1,end,alex+arr[start],lee,count+1,visited),self.backtrack(arr,start,end-1,alex+arr[end],lee,count+1,visited))
            else:                b=max(self.backtrack(arr,start+1,end,alex,lee+arr[start],count+1,visited),self.backtrack(arr,start,end-1,alex,lee+arr[end],count+1,visited))
            visited[start][end]=max(visited[start][end],a,b)
            return visited[start][end]    
                
    def stoneGame(self, piles: List[int]) -> bool:
        n=len(piles)
        visited=[-1 for i in range(n)]
        for i in range(n):
            visited[i]=[-1 for i in range(n)]
        
        if self.backtrack(piles,0,len(piles)-1,0,0,0,visited):
            return True
        return False
        
        
        


from functools import lru_cache
class Solution:
    def stoneGame(self, piles: List[int]) -> bool:
        N = len(piles)

        @lru_cache(None)
        def dp(i, j):
            # The value of the game [piles[i], piles[i+1], ..., piles[j]].
            if i > j: return 0
            parity = (j - i - N) % 2
            if parity == 1:  # first player
                return max(piles[i] + dp(i+1,j), piles[j] + dp(i,j-1))
            else:
                return min(-piles[i] + dp(i+1,j), -piles[j] + dp(i,j-1))

        return dp(0, N - 1) > 0

class Solution:
    def stoneGame(self, piles: List[int]) -> bool:
        A = piles
        Ans = {}
        def hello(st,end,turn):
            if st > end:
                return 0
            if Ans.get((st,end),None) != None:
                return  Ans[(st,end)]
            if turn%2 == 0:
                t = max(A[st]+hello(st+1,end,turn+1),A[end]+hello(st,end-1,turn+1))
                Ans[(st,end)] = t
                return t
            else:
                t = min(hello(st+1,end,turn+1)-A[st],hello(st,end-1,turn+1)-A[end])
                Ans[(st,end)] = t
                return t
        t = hello(0,len(A)-1,0)
        return t > 0

class Solution:
    def stoneGame(self, piles: List[int]) -> bool:
        n = len(piles)
        dp = [[-1 for _ in range(n) ] for _ in range(n)]

        def score_helper(l, r):
            if l > r:
                return 0
            if l == r:
                return piles[l]
            if dp[l][r] != -1:
                return dp[l][r]
            dp[l][r] = max(piles[l] - dp[l+1][r], piles[r]-dp[l][r-1])
            return score_helper(0, n-1)
        
        return score_helper(0, n-1) >= 0

class Solution:
    def stoneGame(self, piles: List[int]) -> bool:
        n = len(piles)
        mat = [[[0,0] for c in range(n)] for r in range(n)]
        for r in range(n):
            mat[r][r][0] = piles[r]
        for diff in range(1,n):
            for r in range(0, n-diff):
                c = r + diff
                left_ = mat[r][c-1]
                picker_1 = left_[1]+piles[c]
                other_1 = left_[0]
                right_ = mat[r+1][c]
                picker_2 = right_[1] + piles[r]
                other_2 = right_[0]
                mat[r][c] = (max(picker_1, picker_2), min(other_1, other_2))
                
        if mat[-1][-1][0] > mat[-1][-1][1]:
            return True
        return False


class Solution:
    def stoneGame(self, piles: List[int]) -> bool:
        n = len(piles)
        dp = {}
        
        for i in range(n):
            dp[(i,i)] = [piles[i],0]
        
        for i in range(n - 2, - 1,-1):
            for j in range(i + 1,n):
                left = [dp[(i + 1,j)][1] + piles[i],dp[(i + 1,j)][0]]
                right = [dp[(i,j - 1)][1] + piles[j],dp[(i,j - 1)][0]]

                dp[(i,j)] = max ( left ,right)         
        return dp[(0,n - 1)][0] > dp[(0,n - 1)][1]

from functools import lru_cache
@lru_cache(maxsize=None)
class Solution:
    def stoneGame(self, piles: List[int]) -> bool:
        A = piles
        Ans = {}
        def hello(st,end,turn):
            if st > end:
                return 0
            if Ans.get((st,end),None) != None:
                return  Ans[(st,end)]
            if turn%2 == 0:
                t = max(A[st]+hello(st+1,end,turn+1),A[end]+hello(st,end-1,turn+1))
                Ans[(st,end)] = t
                return t
            else:
                t = min(hello(st+1,end,turn+1)-A[st],hello(st,end-1,turn+1)-A[end])
                Ans[(st,end)] = t
                return t
        t = hello(0,len(A)-1,0)
        return t > 0

class Solution:
    def stoneGame(self, piles: List[int]) -> bool:
        self.mp = {}
        t = self.foo(0, len(piles) - 1, piles)
        return sum(piles) < 2 * t

    def foo(self, i, j, p):
        if i == j:
            return p[i]
        
        key = str(i) + str(j)
        if key in self.mp:
            return self.mp[key]
        v = max(
            p[i] + self.foo(i + 1, j, p),
            p[j] + self.foo(i, j - 1, p),
        )
        
        self.mp[key] = v
        return v


class Solution:
    def stoneGame(self, piles: List[int]) -> bool:
        self.cache = {}
        self.piles = piles
        return self.minimax(0, len(piles) - 1, True) > 0
    
    def minimax(self, l, r, is_alex):
        if (l, r) in self.cache: return self.cache[(l, r)]
    
        if l > r: return 0
        
        piles = self.piles
        
        if is_alex:
            res = max(self.minimax(l + 1, r, False) + piles[l], self.minimax(l, r - 1, False) + piles[r])
            self.cache[(l, r)] = max(self.cache[(l, r)], res) if (l, r) in self.cache else res
        else:
            res = min(self.minimax(l + 1, r, True) - piles[l], self.minimax(l, r - 1, True) - piles[r])
            self.cache[(l, r)] = max(self.cache[(l, r)], res) if (l, r) in self.cache else res
        return self.cache[(l, r)]

class Solution:
    def stoneGame(self, piles: List[int]) -> bool:
        dp=[[[0,0] for _ in range(len(piles))]for _ in range(len(piles))]
        # print(dp)
        for i in range(len(piles)):
            dp[i][i]=[piles[i],0]
        # print(dp)
        for i in range(len(piles)-1,-1,-1):
            for j in range(i,len(piles)):
                if i==j:
                    continue
                a=max(dp[i+1][j][1]+piles[i],dp[i][j-1][1]+piles[j])
                dp[i][j]=[a,0]
                if dp[i][j][0]==dp[i+1][j][1]+piles[i]:
                    dp[i][j][1]=dp[i+1][j][0]
                else:
                    dp[i][j][1]=dp[i][j-1][0]
        
        if dp[0][len(piles)-1][0]>dp[0][len(piles)-1][1]:
            return True
        return False
                
            


class Solution:
    def stoneGame(self, piles: List[int]) -> bool:
        N = len(piles)
        def dp(i, j):
            # The value of the game [piles[i], piles[i+1], ..., piles[j]].
            if i > j: return 0
            parity = (j - i - N) % 2
            if parity == 1:  # first player
                return max(piles[i] + dp(i+1,j), piles[j] + dp(i,j-1))
            else:
                return min(-piles[i] + dp(i+1,j), -piles[j] + dp(i,j-1))
        
        # this is actually min max tree traversal :D
        @lru_cache(None)
        def recursion(i, j):
            if i > j:
                return 0
            curr_len = (j - i)
            if curr_len % 2 == 0:
                return min(-piles[i] + recursion(i+1, j), -piles[j] + recursion(i, j-1))
            else:
                return max(piles[i] + recursion(i+1, j), piles[j] + recursion(i, j-1))
        
        return recursion(0, N - 1) > 0

class Solution:
    def stoneGame(self, piles: List[int]) -> bool:
        l = len(piles)
        dp = [[[piles[i] * (i == j), 0] for j in range(l)] for i in range(l)]
        for d in range(1, l):
            for w in range(l - d):
                x, y = w, w + d
                l1, l2, r1, r2 = dp[x + 1][y] + dp[x][y - 1]
                dp[x][y] = max([l2 + piles[x], l1], [r2 + piles[y], r1])
        return dp[0][-1][0] > dp[0][-1][1]


class Solution:
    def stoneGame(self, piles: List[int]) -> bool:
        if not piles:
            return False
        n = len(piles)
        return self.helper(0, n-1, piles, 0, 0, 1, {})
    
    def helper(self, left, right, piles, scoreA, scoreB, isPlayerA, memo):
        if left > right:
            return scoreA > scoreB
        
        if (left, right, isPlayerA) in memo:
            return memo[(left, right, isPlayerA)]
        
        if isPlayerA:
            res = self.helper(left+1, right, piles, scoreA + piles[left], scoreB, 1-isPlayerA, memo) or self.helper(left, right-1, piles, scoreA + piles[right], scoreB, 1-isPlayerA, memo)
        else:
            res = self.helper(left+1, right, piles, scoreA, scoreB + piles[left], 1-isPlayerA, memo) or self.helper(left, right-1, piles, scoreA, scoreB + piles[right], 1- isPlayerA, memo)
        
        memo[(left, right, isPlayerA)] = res
        return res
        
        


class Solution:
    def stoneGame(self, piles: List[int]) -> bool:
        n = len(piles)
        dp = [[None] * n for _ in range(n)]
        for i in range(n):
            dp[i][i] = [piles[i], 0]
        for k in range(2, n+1):
            for i in range(n-k+1):
                j = i + k - 1
                first = max(piles[i] + dp[i+1][j][1], piles[j] + dp[i][j-1][1])
                second = min(dp[i+1][j][0], dp[i][j-1][0])
                dp[i][j] = [first, second]
        return dp[0][-1][0] > dp[0][-1][1]

class Solution:
    
    @staticmethod
    def f(piles, start, end, cache, sums):
        if cache[start][end] == -1:
            cache[start][end] = max(
                piles[start] + sums[end + 1] - sums[start + 1] - Solution.f(piles, start + 1, end, cache, sums),
                piles[end] + sums[end] - sums[start] - Solution.f(piles, start, end - 1, cache, sums)
            )
        return cache[start][end]
    
    def stoneGame(self, piles: List[int]) -> bool:
        cache = [[-1] * len(piles) for i in range(len(piles))]
        sums = [0] * (len(piles) + 1)
        for i in range(len(piles)):
            sums[i + 1] = sums[i] + piles[i]
            cache[i][i] = piles[i]
        alex = Solution.f(piles, 0, len(piles) - 1, cache, sums)
        return alex > sums[-1] - alex


from functools import lru_cache

class Solution:
    def stoneGame(self, piles):
        N = len(piles)

        @lru_cache(None)
        def dp(i, j):
            # The value of the game [piles[i], piles[i+1], ..., piles[j]].
            if i > j: return 0
            parity = (j - i) % 2
            if parity == 1:  # first player
                return max(piles[i] + dp(i+1,j), piles[j] + dp(i,j-1))
            else:
                return min(-piles[i] + dp(i+1,j), -piles[j] + dp(i,j-1))

        return dp(0, N - 1) > 0

class Solution:
    def stoneGame(self, piles):
        
        def dp(piles, l, r, memo):
            if l > r:
                return 0
            if (l,r) in memo:
                return memo[(l,r)]
            op1 = piles[l] - dp(piles, l+1, r, memo)
            op2 = piles[r] - dp(piles, l, r-1, memo)
            stone = max(op1, op2)
            memo[(l,r)] = stone
            return stone
        
        return dp(piles, 0, len(piles)-1, {}) > 0
            
            


class Solution:
    def stoneGame(self, piles: List[int]) -> bool:
        @lru_cache(None)
        def dfs(i, j, isAlex):
            if j < i: return 0
            elif i == j: return piles[i] if isAlex else -piles[i]
            if isAlex:
                return max(piles[i]+dfs(i+1, j, not isAlex), piles[j]+dfs(i, j-1, not isAlex))
            else:
                return min(-piles[i]+dfs(i+1, j, not isAlex), -piles[j]+dfs(i, j-1, not isAlex))
        
        if not piles: return False
        n = len(piles)
        
        return dfs(0, n-1, True) > 0
    
    def stoneGame(self, piles: List[int]) -> bool:
        if not piles: return False
        n = len(piles)
        nums = piles
        dp = [[[None, None] for _ in range(n)] for _ in range(n)]
        for i in range(n):
            dp[i][i][0] = -nums[i]
            dp[i][i][1] = nums[i]
        for l in range(1, n):
            for i in range(n-l):
                j = i+l
                dp[i][j][0] = min(-nums[i]+dp[i+1][j][1], -nums[j]+dp[i][j-1][1])
                dp[i][j][1] = max(nums[i]+dp[i+1][j][0], nums[j]+dp[i][j-1][0])
                
        return dp[0][n-1][1] > 0

class Solution:
    def stoneGame(self, piles: List[int]) -> bool:
        n = len(piles)
        self.memo = [[float('-inf') for _ in range(n)] for _ in range(n)]
        return self.dfs(piles, 0, n - 1) > 0
    
    def dfs(self, piles, left, right):
        if left == right:
            return piles[left]
        
        if self.memo[left][right] == float('-inf'):
            self.memo[left][right] = max(piles[left] - self.dfs(piles, left + 1, right), piles[right] - self.dfs(piles, left, right - 1))
        
        return self.memo[left][right]


class Solution:
    def stoneGame(self, piles: List[int]) -> bool:
        memo = dict()
        return self.find(piles, 0, 0, True, 0, len(piles)-1, memo)
        
    def find(self, piles, a_score, b_scord, is_a, front, end, memo):
        if front > end:
            return a_score > b_scord
        
        key = (front, end)
        if key in memo:
            return memo[key]
        
        
        if is_a:
            res = self.find(piles, a_score + piles[front], b_scord, not is_a, front + 1, end, memo) or self.find(piles, a_score + piles[end], b_scord, not is_a, front, end-1, memo)
        else:
            res = self.find(piles, a_score, b_scord + piles[front], not is_a, front + 1, end, memo) or self.find(piles, a_score, b_scord + piles[end], not is_a, front, end-1, memo)
        
        memo[key] = res
        return res
        


class Solution:
    def stoneGame(self, piles: List[int]) -> bool:
        return self.dfs(piles, 0, len(piles) - 1, {})
        
    def dfs(self, piles, start, end, memo):
        if start > end:
            return 0
        elif start == end:
            return piles[start]
        elif (start, end) in memo:
            return memo[(start, end)]
        
        # choose one which is most optimal for the player
        L = piles[start] - self.dfs(piles, start + 1, end, memo)
        R = piles[end] - self.dfs(piles, start, end - 1, memo)
        memo[(start, end)] = max(L, R)
        return memo[(start, end)]

class Solution:
    def stoneGame(self, piles: List[int]) -> bool:
        @lru_cache(None)
        def dfs(i, j):
            if i == j:
                return piles[i]
            
            return max(piles[i] - dfs(i + 1, j), piles[j] - dfs(i, j - 1))
        
        return dfs(0, len(piles) - 1) > 0

class Solution:
    from functools import lru_cache
    def stoneGame(self, piles: List[int]) -> bool:
        n = len(piles)
        
        @lru_cache(None)
        def dp(i, j, asum, lsum, aturn):
            
            if i > j:
                return (0, 0)
            
            if aturn:
                asum += max(piles[i] + dp(i+1, j, asum, lsum, False)[0], piles[j] + dp(i, j-1, asum, lsum, False)[0])
            else:
                lsum += max(piles[i] + dp(i+1, j, asum, lsum, False)[1], piles[j] + dp(i, j-1, asum, lsum, False)[1])
            
            return (asum, lsum)
        
        asum, lsum = dp(0, n-1, 0, 0, True)

        return bool(asum - lsum)

from functools import lru_cache

class Solution:
    def stoneGame(self, piles):
        N = len(piles)

        @lru_cache(None)
        def dp(i, j):
            # The value of the game [piles[i], piles[i+1], ..., piles[j]].
            if i > j: return 0
            parity = (j - i - N) % 2
            if parity == 1:  # first player
                return max(piles[i] + dp(i+1,j), piles[j] + dp(i,j-1))
            else:
                return min(-piles[i] + dp(i+1,j), -piles[j] + dp(i,j-1))

        return dp(0, N - 1) > 0

class Solution:
    def stoneGame(self, piles: List[int]) -> bool:
        @lru_cache(None)
        def dp(i, j):
            if i + 1 == j:
                arr = piles[i + 1: j + 1]
                return max(arr) - min(arr)
            
            
            L, R = piles[i], piles[j]
            
            return max(L - R + dp(i + 1, j), R - L + dp(i, j - 1))
        
        return dp(0, len(piles) - 1) > 0


class Solution:
    def stoneGame(self, piles: List[int]) -> bool:
        self.f_map, self.s_map = dict(), dict()
        _sum = sum(piles)
        alex = self.f(piles, 0, len(piles)-1)
        return alex > _sum/2
    
    def f(self, piles, start, end):
        if start == end:
            return piles[start]
        if ((start, end) not in self.f_map):
            v_val = max(piles[start] + self.s(piles, start + 1, end), piles[end] + self.s(piles, start, end-1))
            self.f_map[(start, end)] = v_val
        return self.f_map[(start, end)]
    
    def s(self, piles, start, end):
        if start == end:
            return piles[start]
        if ((start, end) not in self.s_map):
            v_val = max(piles[start] + self.f(piles, start + 1, end), piles[end] + self.f(piles, start, end-1))
            self.s_map[(start, end)] = v_val
        return self.s_map[(start, end)]

class Solution:
    def stoneGame(self, piles: List[int]) -> bool:
        if len(piles) == 0:
            return False
        ans = []
        l = len(piles)
        for i in range(l):
            ans.append(max(piles[0], piles[-1]))
            piles.remove(max(piles[0], piles[-1]))
            print(ans)
        if ans[-2]>=ans[-1]:
            return True

from functools import lru_cache
class Solution:
    def stoneGame(self, piles: List[int]) -> bool:
    

        @lru_cache(None)
        def dp(i, j):
            if i > j:
                return 0
            term = (j - i) % 2
            if term == 1:
                return max(dp(i + 1, j) + piles[i] , dp(i, j -1) + piles[j])
            else:
                return min(dp(i + 1, j) - piles[i] , dp(i, j - 1) - piles[j])
        return dp(0, len(piles) - 1) > 0

class Solution:
    def stoneGame(self, piles: List[int]) -> bool:
        n = len(piles)
        @lru_cache(None)
        def sumRange(i, j):
            if i == j: return piles[i]
            else: return piles[i] + sumRange(i + 1, j)
        @lru_cache(None)
        def dp(i, j):
            if i == j:
                return piles[i]
            else:
                return max(piles[i] + sumRange(i+1, j) - dp(i + 1, j),
                          piles[j] + sumRange(i, j - 1) - dp(i, j - 1))
        Alex = dp(0, n-1)
        Lee = sumRange(0, n-1) - Alex
        return Alex > Lee

class Solution:
    def stoneGame(self, piles: List[int]) -> bool:
        cache = {}
        def firstscore(i, j):
            if i >= j: 
                return 0
            # if j == i+1 and j < len(piles): #because [i, j)
            #     return piles[i] 
            if (i, j) in cache:
                return cache[i, j]
            res = max(piles[i] + min(firstscore(i+2, j), firstscore(i+1, j-1)), 
                              piles[j - 1] + min(firstscore(i+1, j-1), firstscore(i, j-2)))
            cache[i, j] = res
            return cache[i, j]
        Alex = firstscore(0, len(piles))
        Lee = sum(piles) - Alex
        return Alex > Lee
        


import numpy as np
class Solution:
    def stoneGame(self, piles: List[int]) -> bool:
        n = len(piles)
        dp = np.empty((n,n))
        for j in range(1,n):
            dp[j-1,j] = abs(piles[j-1]-piles[j])

        for j in range(3,n,2):
            for i in range(0,n-j):
                #want to get dp[i,i+j]
                #crrespond dp[i,i+j-2] dp[i+1,i+j-1],dp[i-2,i+j]
                temp1 = piles[i+j]+min(-piles[i+j-1]+dp[i,i+j-2],-piles[i]+dp[i+1,i+j-1])
                temp2 = piles[i]+min(-piles[i+1]+dp[i+2,i+j],-piles[i+j]+dp[i+1,i+j-1])
                dp[i,i+j] = max(temp1,temp2)
        if dp[0,n-1]>0:
            return True
        else: return False


class Solution:
    def stoneGame(self, piles: List[int]) -> bool:
        dp = {}
        def dfs(i, j, Alex, Lee, who):
            if (i, j) not in dp:
                if i > j:
                    return Alex, Lee
                if who:
                    Alextmp1, Leetmp1 = dfs(i + 1, j - 0, Alex + piles[i], Lee, not who)
                    Alextmp2, Leetmp2 = dfs(i + 0, j - 1, Alex + piles[j], Lee, not who)
                    if Alextmp1 - Alex > Alextmp2 - Alex:
                        dp[i, j] = Alextmp1 - Alex, Leetmp1 - Lee
                    else:
                        dp[i, j] = Alextmp2 - Alex, Leetmp2 - Lee
                else:
                    Alextmp1, Leetmp1 = dfs(i + 1, j - 0, Alex, Lee + piles[i], not who)
                    Alextmp2, Leetmp2 = dfs(i + 0, j - 1, Alex, Lee + piles[j], not who)
                    if Leetmp1 - Lee > Leetmp2 - Lee:
                        dp[i, j] = Alextmp1 - Alex, Leetmp1 - Lee
                    else:
                        dp[i, j] = Alextmp2 - Alex, Leetmp2 - Lee
            return Alex + dp[i, j][0], Lee + dp[i, j][1]

        Alex, Lee = dfs(0, len(piles) - 1, 0, 0, True)
        #print(Alex, Lee)
        if Alex > Lee:
            return True
        else:
            return False


class Solution:
    def stoneGame(self, piles: List[int]) -> bool:
        self.result_cache = {}
        def f(low, high, nums):
            if low > high:
                return 0
            if low == high:
                return nums[low]
            if (low, high) in self.result_cache:
                return self.result_cache[(low, high)]
            l = nums[low]  + min(f(low + 2, high, nums), f(low + 1, high - 1 , nums))
            h = nums[high] + min(f(low + 1, high - 1, nums), f(low, high - 2, nums))
            r = max(l, h)
            self.result_cache[(low, high)] = r
            return r
        p1 = f(0, len(piles) - 1, piles)
        p2 = sum(piles) - p1
        return p1 > p2


class Solution:
    def dp(self, i, j):
        if (i, j) in self.memo:
            return self.memo[(i, j)]
        if i > j:
            return (0, 0)
        
        firstTakeLeft, firstTakeRight = self.piles[i] + self.dp(i+1, j)[1], self.piles[j] + self.dp(i, j-1)[1]
        if firstTakeLeft > firstTakeRight:
            self.memo[(i, j)] = (firstTakeLeft, self.dp(i+1,j)[0])
        else:
            self.memo[(i, j)] = (firstTakeRight, self.dp(i, j-1)[0])
        
        return self.memo[(i, j)]

    def stoneGame(self, piles: List[int]) -> bool:
        self.piles = piles
        self.memo = {}

        for i in range(len(piles)):
            self.memo[(i, i)] = (piles[i], 0)
        
        fir, sec = self.dp(0, len(piles)-1)

        return fir >= sec

class Solution:
    def stoneGame(self, piles: List[int]) -> bool:
        memo = [[-1 for _ in range(len(piles))] for _ in range(len(piles))]
        return self.recursive(0, 0, len(piles) - 1, 0, 0, piles, memo)
    
    def recursive(self, turn, left_idx, right_idx, sum1, sum2, piles, memo):
        # Base Case
        if left_idx >= right_idx:
            return sum1 > sum2
        
        if memo[left_idx][right_idx] != -1:
            return memo[left_idx][right_idx]
        
        
        if turn % 2 == 0:
            res = self.recursive(turn + 1, left_idx + 1, right_idx, sum1 + piles[left_idx], sum2, piles, memo) or self.recursive(turn + 1, left_idx, right_idx - 1, sum1 + piles[right_idx], sum2, piles, memo)
        else:
            res =  self.recursive(turn + 1, left_idx + 1, right_idx, sum1, sum2 + piles[left_idx], piles, memo) or self.recursive(turn + 1, left_idx, right_idx - 1, sum1, sum2 + piles[right_idx], piles, memo)
        
        memo[left_idx][right_idx] = res
        return memo[left_idx][right_idx]

class Solution:
    def stoneGame(self, piles: List[int]) -> bool:
        
        memo = {}
        def netWin(left, right):
            
            if (left, right) not in memo:
                if left > right:
                    return 0
                
                memo[(left, right)] = -float('inf')
                memo[(left, right)] = max(memo[(left, right)], piles[left] - netWin(left + 1, right))
                memo[(left, right)] = max(memo[(left, right)], piles[right] - netWin(left, right - 1))
                
            return memo[(left, right)]
        
        res = netWin(0, len(piles) - 1)
        # print (memo, res)
        return True if res > 0 else False

class Solution:
    def stoneGame(self, piles: List[int]) -> bool:
        n = len(piles)
        
        @lru_cache(None)
        # dp(i, j) max net score alex can get
        def dp(i, j):
            if i > j:
                return 0
            if (n - j + i) % 2 == 1: # alex plays
                return max(piles[i] + dp(i + 1, j), piles[j] + dp(i, j - 1))
            return min(dp(i + 1, j) - piles[i], dp(i, j - 1) - piles[j])
        return dp(0, n - 1) > 0


class Solution:
    def stoneGame(self, piles: List[int]) -> bool:
        
        memo = {}
        def netWin(left, right):
            
            if (left, right) not in memo:
                if left > right:
                    return 0
                
                memo[(left, right)] = -float('inf')
                memo[(left, right)] = max(memo[(left, right)], piles[left] - netWin(left + 1, right))
                memo[(left, right)] = max(memo[(left, right)], piles[right] - netWin(left, right - 1))
                
            return memo[(left, right)]
        
        res = netWin(0, len(piles) - 1)
        # print (memo, res)
        return True if res > 0 else False


class Solution:
    def stoneGame(self, piles: List[int]) -> bool:
        dp = [[[0 for i in range(2)] for z in range(len(piles))] for j in range(len(piles))]
        for i in range(len(dp)):
            dp[i][i] = [piles[i], 0]
 
        for i in range(len(dp)-2, -1, -1):
            for j in range(i+1, len(dp[0])):
                left = piles[i] + dp[i+1][j][1]
                right = piles[j] + dp[i][j-1][1]
                if left > right:
                    dp[i][j][0] = left
                    dp[i][j][1] = dp[i+1][j][0]
                else:
                    dp[i][j][0] = right
                    dp[i][j][1] = dp[i][j-1][0]
        res = dp[0][-1]
        if dp[0][-1][0] - dp[0][-1][1] > 0:
            return True
        else:
            return False


class Solution:
    def stoneGame(self, piles: List[int]) -> bool:
        l = len(piles)
        dp = [[-1 for i in range(l)] for j in range(l)]
        def solve(piles, i, j, tot):
            alex = (j-i-l) % 2
            if i == j:
                if alex:
                    tot += piles[i]
                return tot > 0

            if dp[i][j] != -1:
                return dp[i][j]
            if alex:
                if solve(piles, i+1, j, tot+piles[i]):
                    dp[i][j] = True
                    return True
                dp[i][j]= solve(piles, i, j-1, tot+piles[j])
                return dp[i][j]
            else:
                if solve(piles, i+1, j, tot-piles[i]):
                    dp[i][j] = True
                    return True
                dp[i][j]= solve(piles, i, j-1, tot-piles[j])
                return dp[i][j]
            
        return solve(piles, 0, l-1, 0)

class Solution:
    def stoneGame(self, piles: List[int]) -> bool:
        n = len(piles)
        table = [[False] * (n+1) for _ in range(n+1)]
        
        for i in range(n+1):
            table[i][i] = True
        
        for row in range(n-1, -1, -1):
            for col in range(row, n+1):
                if table[row][col-1] == False:
                    table[row][col] = True
                if table[row+1][col] == False:
                    table[row][col] = True
        return table[0][n]

class Solution:
    def stoneGame(self, piles: List[int]) -> bool:
        self.dp = [[None for i in range(len(piles))] for i in range(len(piles))]
        self.func(piles, 0, 0, len(piles)-1, 0, 0)
        return self.dp[0][len(piles)-1]
    
    
    def func(self, arr, turn, i, j, a, b):
        if self.dp[i][j] == True:
            return True
        elif self.dp[i][j] == False:
            return False

        if  i == j:
            b += arr[i]
            self.dp[i][j] = a > b
            return self.dp[i][j]

        if not turn:
            self.dp[i][j] = self.func(arr, turn^1, i+1, j, a+arr[i], b) or self.func(arr, turn^1, i, j-1, a+arr[j], b)
            return self.dp[i][j]
        else:
            self.dp[i][j] = self.func(arr, turn^1, i+1, j, a, b+arr[i]) or self.func(arr, turn^1, i, j-1, a, b+arr[j])
            return self.dp[i][j]
    
    
        
    # Gives TLE
    # def recur(self, arr, turn, a, b):
    #     if len(arr) == 1:
    #         b += arr[0]
    #         return a > b
    #     if not turn:
    #         return self.recur(arr[1:], turn^1, a+arr[0], b) or self.recur(arr[:-1], turn^1, a+arr[-1], b)
    #     else:
    #         return self.recur(arr[1:], turn^1, a, b+arr[0]) or self.recur(arr[:-1], turn^1, a, b+arr[-1])


class Solution:
    def stoneGame(self, piles: List[int]) -> bool:
        dp = piles.copy()
        for i in range(len(piles)-2, -1, -1):
            for j in range(i+1, len(piles)):
                dp[j] = max(piles[i] - dp[j], piles[j] - dp[j - 1])
        
        return dp[len(dp) - 1] > 0


class Solution:
    def stoneGame(self, piles: List[int]) -> bool:
        n = len(piles)
        dp = [0] * n
        for i in range(n):
            for j in range(i, -1 , -1):
                if i == j:
                    dp[i] = piles[i]
                else:
                    dp[j] = max(piles[i] - dp[j], piles[j] - dp[j+1])
        return dp[0] > 0

class Solution:
    def stoneGame(self, piles: List[int]) -> bool:
        n = len(piles)
        dp = [piles[0]] * n 
        for j in range(1, n):
            dp[j] = piles[j]
            for i in range(j-1, -1 ,-1):
                dp[i] = max(piles[i] - dp[i+1], piles[j] - dp[i])
            #print(dp)
                
        return dp[0] > 0
        


class Solution:
    def stoneGame(self, piles: List[int]) -> bool:
        n = len(piles)
        dp = piles[:]
        for d in range(1, n):
            for i in range(n - d):
                dp[i] = max(piles[i] - dp[i + 1], piles[i + d] - dp[i])
        return dp[0] > 0

class Solution:
    def stoneGame(self, piles: List[int]) -> bool:
        n = len(piles)
        dp = [0] * n
        # i is rightbound
        for i in range(n):
            # j is leftbound
            for j in range(i, -1, -1):
                if i == j:
                    dp[i] = piles[i]
                else:
                    dp[j] = max(piles[i] - dp[j], piles[j] - dp[j+1])
        return dp[0] > 0

class Solution:
    def stoneGame(self, piles: List[int]) -> bool:
        # Let f(i,j) be the maximum difference Alex-Lee
        # Key idea: If Alex takes pile[i], then Lee will play optimally to get a score of f(i+1, j) for him,
        # which is equilvalent to Alex getting a score of -f(i+1, j). So Alex's total score is pile[i] - f(i+1,j)
        # Then just take the pile that results in maximum score.
        # f(i,j) = max(piles[i] - f(i+1,j), piles[j] - f(i,j-1))
        # Base case: f(i,i) = piles[i]
        # If you draw the 2d grid, it looks like filling in diagonal order
        # Can do space optimization using 1D DP
        n = len(piles)
        if n == 1:
            return True
        
        dp = piles[:]  # Base row        
        for l in range(1, n):
            for i in range(n-l-1, -1, -1):
                j = i+l
                dp[j] = max(piles[i] - dp[j], piles[j] - dp[j-1])
                
        return dp[-1] > 0

class Solution:
    def stoneGame(self, piles: List[int]) -> bool:
        payoffs = piles
        r = 1
        while len(payoffs) > 1:
            new_payoffs = []
            for i in range(len(payoffs) - 1):
                new_payoffs.append(max(piles[i] - payoffs[i+1], piles[i + r] - payoffs[i]))
            payoffs = new_payoffs
            r += 1
        return payoffs[0] > 0


class Solution:
    def stoneGame(self, piles: List[int]) -> bool:
        n = len(piles)
        dp = piles[:]
        for d in range(1,n):
            for i in range(n-d):
                dp[i] =  max(piles[i]-dp[i+1], piles[i+d]-dp[i])
        return dp[0]>0


class Solution:
    def stoneGame(self, piles: List[int]) -> bool:
        pre_s = [0]
        acc = 0
        for num in piles:
            acc += num
            pre_s.append(acc)
        
        m = len(piles)
        dp = [[0] * m for _ in range(m)]
        
        for i in reversed(list(range(m))):
            for j in range(i, m):
                if i == j:
                    dp[i][j] = piles[i]
                else:
                    s = pre_s[j+1] - pre_s[i]
                    if dp[i+1][j] < dp[i][j-1]:
                        dp[i][j] = s - dp[i+1][j]
                    else:
                        dp[i][j] = s - dp[i][j-1]
        
        return dp[0][-1] > dp[1][-1] or dp[0][-1] > dp[0][-2]


class Solution:
    def stoneGame(self, piles: List[int]) -> bool:
        n = len(piles)
        memo = piles[:]
        for l in range(2, n+1):
            for i in range(n+1-l):
                memo[i] = max(piles[i] - memo[i+1], piles[i+l-1] - memo[i])
        return memo[0]    

from functools import lru_cache

class Solution:
    def stoneGame(self, piles: List[int]) -> bool:
        # Mathematical
        # If Alex takes the first pile initially, she can always take the third pile. If she takes the fourth pile initially, she can always take the second pile. At least one of first + third, second + fourth is larger, so she can always win.
        # O(1)
        # return True


        # Dynamic Programming
        # Time  complexity: O(N^2)
        # Space complexity: O(N^2)
        # N = len(piles)

        # @lru_cache(None)
        # def dp(i, j):
        #     if i > j: return 0
        #     parity = (j - i - N) % 2
        #     if parity == 1: # first player
        #         return max(piles[i] + dp(i + 1, j), piles[j] + dp(i, j - 1))
        #     else:
        #         return min(-piles[i] + dp(i + 1, j), -piles[j] + dp(i, j - 1))

        # return dp(0, N - 1) > 0


        # N = len(piles)
        # dp = [[0] * N for i in range(N)]
        # for i in range(N):
        #     dp[i][i] = piles[i]
        # for d in range(1, N):
        #     for i in range(N - d):
        #         dp[i][i + d] = max(piles[i] - dp[i + 1][i + d], piles[i + d] - dp[i][i + d - 1])

        # return dp[0][-1] > 0


        N = len(piles)
        dp = piles[:]
        for d in range(1, N):
            for i in range(N - d):
                dp[i] = max(piles[i] - dp[i + 1], piles[i + d] - dp[i])
        return dp[0] > 0


class Solution:
    def stoneGame(self, piles: List[int]) -> bool:
        N = len(piles)
        dp = [[0] * N for _ in range(N)]
        for i in range(N):
            dp[i][i] = piles[i]
        for i in range(N):
            for j in range(i + 1, N):
                dp[i][j] = max(piles[i] - dp[i + 1][j], piles[j] - dp[i][j - 1])
        
        return dp[i][-1] > 0

class Solution:
    def stoneGame(self, piles: List[int]) -> bool:
        n = len(piles)
        dp = [[0] * n for _ in range(n)]

        # Init
        for i in range(n):
            dp[i][i] = piles[i]
        
        for i in range(n-1, -1, -1):
            for j in range(i+1, n):
                dp[i][j] = max(piles[i] - dp[i+1][j], piles[j] - dp[i][j-1])
        
        return dp[0][-1] > 0

class Solution:
    def stoneGame(self, nums: List[int]) -> bool:
        n, f = len(nums), [i for i in nums]
        for i in range(1, n):
            for j in range(n-i):
                f[j] = max(nums[j]-f[j+1], nums[j+i]-f[j])
        return f[0] > 0

class Solution:
    def stoneGame(self, piles: List[int]) -> bool:
        # condition on first dp[i,j] is the number of stones greater than the opponent if both using the optimum strate
        # take first, dp[0][n-1] = max(piles[0] - dp[1][n-1], piles[n-1] - dp[0][n-2])
        # dp[i][j] = max(piles[i]-dp[i+1][j], piles[j]-dp[i][j+1]
        # return dp[0][n-1]
        n = len(piles)
        dp = [[0]*n for _ in range(n)]
        
        # initialize
        for i in range(n):
            dp[i][i] = piles[i]
            
        for l in range(1, n):
            for i in range(n-l):
                j = i + l
                dp[i][j] = max(piles[i]-dp[i+1][j], piles[j]-dp[i][j-1])
            # print(dp)
            
        return dp[0][n-1] > 0

class Solution:
    def stoneGame(self, piles: List[int]) -> bool:
        N = len(piles)
        dp = [[0] * N for _ in range(N)]
        for i in range(N):
            dp[i][i] = piles[i]
        
        # j - i = d start from the shortest subarray
        for d in range(1, N):
            for i in range(N - d):
                j = d + i
                dp[i][j] = max(piles[i] - dp[i + 1][j], piles[j] - dp[i][j - 1])
        
        return dp[0][-1] > 0

class Solution:
    def stoneGame(self, piles: List[int]) -> bool:
        n = len(piles)
        dp = [[0]*n for _ in range(n)]
        for i in range(n): dp[i][i] = piles[i]
        for l in range(1, n):
            for i in range(n-l):
                j = i + l
                dp[i][j] = max(piles[i] - dp[i+1][j], piles[j] - dp[i][j-1])
        return dp[0][-1] > 0

class Solution:
    def stoneGame(self, piles: List[int]) -> bool:
        n = len(piles)
        dp = [[0] * n for _ in range(n)]
        for i in range(n):
            dp[i][i] = piles[i]
        for k in range(1, n):
            for i in range(n-k):
                j = i + k
                # print(i, j, k)
                dp[i][j] = max(piles[i] - dp[i+1][j], piles[j] - dp[i][j-1])
        return dp[0][-1] > 0

class Solution:
    def stoneGame(self, piles: List[int]) -> bool:
        n = len(piles)
        f = [0] * n
        for i in range(n - 1, -1, -1):
            for j in range(i + 1, n):
                f[j] = max(piles[i] - f[j], piles[j] - f[j - 1])
        return f[n - 1] > 0

class Solution:
    def stoneGame(self, piles: List[int]) -> bool:
        n = len(piles)
        dp = [[0] * n for _ in range(n)]
        for i in range(n):
            dp[i][i] = piles[i]
        for d in range(1, n):
            for i in range(n - d):
                j = i + d
                dp[i][j] = max(piles[i] - dp[i + 1][j], piles[j] - dp[i][j - 1])
        return dp[0][-1] > 0
        
            


class Solution:
    def stoneGame(self, piles: List[int]) -> bool:
        # Let f(i,j) be the maximum difference Alex-Lee
        # Key idea: If Alex takes pile[i], then Lee will play optimally to get a score of f(i+1, j) for him,
        # which is equilvalent to Alex getting a score of -f(i+1, j). So Alex's total score is pile[i] - f(i+1,j)
        # Then just take the pile that results in maximum score.
        # f(i,j) = max(piles[i] - f(i+1,j), piles[j] - f(i,j-1))
        # Base case: f(i,i) = piles[i]
        # If you draw the 2d grid, it looks like filling in diagonal order
        # Can do space optimization using 1D DP
        n = len(piles)
        if n == 1:
            return True
        
        # First let's do 2D DP, space optimize later
        dp = [[None]*n for _ in range(n)]
        for i in range(n):
            dp[i][i] = piles[i]
        
        for l in range(1, n):
            for i in range(n-l):
                j = i+l
                dp[i][j] = max(piles[i] - dp[i+1][j], piles[j] - dp[i][j-1])
                
        return dp[0][n-1] > 0

class Solution:
    def stoneGame(self, piles):
        n = len(piles)
        dp = [[0] * n for _ in range(n)]
        for i in range(n):
            dp[i][i] = piles[i]
        for d in range(1, n):
            for i in range(n-d):
                dp[i][i+d] = max(piles[i] - dp[i+1][i+d], piles[i+d] - dp[i][i+d-1])
        return dp[0][-1] > 0


class Solution:
    def stoneGame(self, piles: List[int]) -> bool:
        # dp[i][j] represents for piles[i:j + 1], the maximum differnce of Alex - Lee
        n = len(piles)
        dp = [[0 for col in range(n)] for row in range(n)]
        for i in range(n):
            dp[i][i] = piles[i]
            
        for i in range(n - 1, -1 , -1):
            for j in range(i + 1, n):
                dp[i][j] = max(piles[i] - dp[i + 1][j], piles[j] - dp[i][j - 1])
                
        return dp[0][n - 1] > 0

# 877. Stone Game
    
    # It's tricky when we have even number of piles of stones.
    # You may not have this condition in an interview.

    # Follow-up:

    # What if piles.length can be odd?
    # What if we want to know exactly the diffenerce of score?
    # Then we need to solve it with DP.

    # dp[i][j] means the biggest number of stones 
    # you can get more than opponent picking piles in piles[i] ~ piles[j].
    # You can first pick piles[i] or piles[j].

    # If you pick piles[i], your result will be piles[i] - dp[i + 1][j]
    # If you pick piles[j], your result will be piles[j] - dp[i][j - 1]
    # So we get:
    # dp[i][j] = max(piles[i] - dp[i + 1][j], piles[j] - dp[i][j - 1])
    # We start from smaller subarray and then we use that to calculate bigger subarray.

    # Note that take evens or take odds, it's just an easy strategy 
    # to win when the number of stones is even.
    # It's not the best solution!
    # I didn't find a tricky solution when the number of stones is odd (maybe there is).
    
class Solution1: # 2D DP    
    def stoneGame(self, piles: List[int]) -> bool:
        p = piles
        n = len(p)
        
        dp = [[0] * n for i in range(n)]
        for i in range(n): 
            dp[i][i] = p[i]
            
        for d in range(1, n):
            for i in range(n - d):
                dp[i][i + d] = max(p[i] - dp[i + 1][i + d], p[i + d] - dp[i][i + d - 1])
                
        return dp[0][-1] > 0
    
    
class Solution: # 1D DP, Space: O(N)    
    def stoneGame(self, p):
        n = len(p)
        dp = p[:]
        for d in range(1, n):
            for i in range(n - d):
                # 这次拿完会赢，下次？？？？
                dp[i] = max(p[i] - dp[i + 1], p[i + d] - dp[i])
        return dp[0] > 0
    
    


class Solution:
    def stoneGame(self, piles: List[int]) -> bool:
        n = len(piles)
        dp = [[0] * n for _ in range(n)]
        for i in range(n): dp[i][i] = piles[i]
        s = sum(piles)
        
        for l in range(1, n):
            for i in range(n - l):
                j = i + l
                dp[i][j] = max(piles[i] + s - dp[i+1][j], piles[j] + s - dp[i][j-1])
                
        return dp[0][n - 1] > (s // 2)

class Solution:
    def stoneGame(self, p):
        n = len(p)
        dp = [[0] * n for i in range(n)]
        for i in range(n): dp[i][i] = p[i]
        for d in range(1, n):
            for i in range(n - d):
                dp[i][i + d] = max(p[i] - dp[i + 1][i + d], p[i + d] - dp[i][i + d - 1])
        return dp[0][-1] > 0
        
    
        
        
                


class Solution:
    def stoneGame(self, piles: List[int]) -> bool:
        if len(piles) == 0:
            return False
        n = len(piles)
        dp = [[0 for _ in range(n)] for _ in range(n)]
        for i in range(n):
            dp[i][i] = piles[i]
        for left in range(n):
            for diff in range(1, n-left):
                right = left + diff
                dp[left][right] = max(piles[left] - dp[left+1][right], piles[right] - dp[left][right])
        
        return dp[0][-1] > 0

class Solution:
    def stoneGame(self, piles: List[int]) -> bool:
        if len(piles) == 2:
            return True
        
        alex = 0
        lee = 0
        
        i = 0
        
        while(i < len(piles)):
            
            if i%2 == 0:
                alex += max(piles[0],piles[len(piles)-1])
                piles.remove(max(piles[0],piles[len(piles)-1]))
                
            else:
                lee += min(piles[0],piles[len(piles)-1])
                piles.remove(min(piles[0],piles(len(piles)-1)))
                
        if alex>lee:
            return True
        return False

class Solution:
    def stoneGame(self, piles: List[int]) -> bool:    
        def max_possible_score(i, j):
            if j - i == 1:
                return abs(piles[i] - piles[j])
            return max(piles[i] - max_possible_score(i+1, j), piles[j] - max_possible_score(i, j-1))
        #return max_possible_score(0, len(piles) - 1) > 0
        n = len(piles)
        dp = [[None for _ in range(n)] for _ in range(n)]
        for i in range(n - 1):
            j = i + 1
            dp[i][j] = abs(piles[i] - piles[j])
        for l in range(2, n):    
            for i in range(n - l):
                j = i + l
                dp[i][j] = max(piles[i] - dp[i+1][j], piles[j] - dp[i][j-1])
        return dp[0][n-1] > 0
        
        
            
            
            


class Solution:
    def stoneGame(self, piles: List[int]) -> bool:
        n = len(piles)
        dp = [[None for _ in range(n)] for _ in range(n)]
        for i in range(n - 1):
            j = i + 1
            dp[i][j] = abs(piles[i] - piles[j])
        for l in range(2, n):    
            for i in range(n - l):
                j = i + l
                dp[i][j] = max(piles[i] - dp[i+1][j], piles[j] - dp[i][j-1])
        return dp[0][n-1] > 0
        
        
            
            
            


class Solution:
    def stoneGame(self, piles: List[int]) -> bool:
        prefix = [0]
        for p in piles:
            prefix.append(prefix[-1] + p)
        n = len(piles)
        dp = [0] * n
        dp[n - 1] = piles[n - 1]
        for i in range(n - 2, -1, -1):
            for j in range(i, n):
                a = piles[i] + prefix[j + 1] - prefix[i + 1] - dp[j]
                b = piles[j] + prefix[j] - prefix[i] - dp[j - 1]
                dp[j] = max(a, b)
        return dp[n - 1] > prefix[-1] // 2

class Solution:
    def stoneGame(self, p: List[int]) -> bool:
        n = len(p)
        dp = [[0]*n for _ in range(n)]
        for i in range(n):
            dp[i][i] = p[i]
        for d in range(1, n):
            for i in range(n - d):
                dp[i][i+d] = max(p[i]-dp[i+1][i+d], p[i+d]-dp[i][i+d-1])
        return dp[0][-1] > 0

from functools import lru_cache

class Solution:
    def stoneGame(self, piles: List[int]) -> bool:
        # Mathematical
        # If Alex takes the first pile initially, she can always take the third pile. If she takes the fourth pile initially, she can always take the second pile. At least one of first + third, second + fourth is larger, so she can always win.
        # O(1)
        # return True


        # Dynamic Programming
        # Time  complexity: O(N^2)
        # Space complexity: O(N^2)
        # N = len(piles)

        # @lru_cache(None)
        # def dp(i, j):
        #     if i > j: return 0
        #     parity = (j - i - N) % 2
        #     if parity == 1: # first player
        #         return max(piles[i] + dp(i + 1, j), piles[j] + dp(i, j - 1))
        #     else:
        #         return min(-piles[i] + dp(i + 1, j), -piles[j] + dp(i, j - 1))

        # return dp(0, N - 1) > 0


        N = len(piles)
        dp = [[0] * N for i in range(N)]
        for i in range(N):
            dp[i][i] = piles[i]
        for d in range(1, N):
            for i in range(N - d):
                dp[i][i + d] = max(piles[i] - dp[i + 1][i + d], piles[i + d] - dp[i][i + d - 1])

        return dp[0][-1] > 0


class Solution:
    def stoneGame(self, piles: List[int]) -> bool:
        n = len(piles)
        dp = [[None for _ in range(n)] for _ in range(n)]
        for l in range(1, n):    
            for i in range(n - l):
                j = i + l
                if j == i + 1:
                    dp[i][j] = abs(piles[i] - piles[j])
                else:
                    dp[i][j] = max(piles[i] - dp[i+1][j], piles[j] - dp[i][j-1])
        return dp[0][n-1] > 0
        
        
            
            
            


class Solution:
    def stoneGame(self, piles: List[int]) -> bool:
        dp = [[0] * len(piles) for _ in range(len(piles))]
        for i in range(len(piles)):
            dp[i][i] = piles[i]
        for i in range(len(piles) - 1)[::-1]:
            for j in range(i + 1, len(piles)):
                dp[i][j] = max(piles[i] - dp[i + 1][j], piles[j] - dp[i][j - 1])
        return dp[0][-1] > 0

class Solution:
    def stoneGame(self, piles: List[int]) -> bool:
        n = len(piles)
        dp = [[0 for i in range(n)] for j in range(n)]
        for i in range(n):
            dp[i][i] = piles[i]
        for interval in range(1,n):
            for left in range(n-interval):
                dp[left][left+interval] = max(piles[left]-dp[left+1][left+interval],piles[left+interval] - dp[left][left+interval-1])
        return dp[0][-1]>0

class Solution:
    def stoneGame(self, piles: List[int]) -> bool:
        n=len(piles)
        dp=[[0 for i in range(n)] for j in range(n)]
        for i in range(n):
            dp[i][i]=piles[i]
        for m in range(2,n+1):
            for l in range(n-m+1):
                r=l+m-1
                dp[l][r]=max(piles[l]-dp[l+1][r], piles[r]-dp[l][r-1])
        return dp[0][n-1]>0

class Solution:
    def stoneGame(self, piles: List[int]) -> bool:
        p = piles
        n = len(p)
        dp = [[0] * n for i in range(n)]
        for i in range(n): dp[i][i] = p[i]
        for d in range(1, n):
            for i in range(n - d):
                dp[i][i + d] = max(p[i] - dp[i + 1][i + d], p[i + d] - dp[i][i + d - 1])
        return dp[0][-1] > 0

class Solution:
    def stoneGame(self, piles: List[int]) -> bool:
        # [3,8,5,1]
        return True

class Solution:
    def stoneGame(self, piles: List[int]) -> bool:
        # dp[i][j], total score the Alex can get with pile[i:j + 1]
        
        n = len(piles)
        dp = [[0 for i in range(n)] for j in range(n)]
        
        for l in range(2, n + 1):
            for i in range(n - l + 1):
                j = i + l - 1
                if l % 2 == 0:  # Alex next move
                    dp[i][j] = max(dp[i + 1][j] + piles[i], dp[i][j - 1] + piles[j])
                else:
                    dp[i][j] = min(dp[i + 1][j] - piles[i], dp[i][j - 1] - piles[j])

                    
        return dp[0][n - 1] > 0

class Solution:
    def stoneGame(self, piles: List[int]) -> bool:
        if not piles or len(piles) == 0:
            return False
        
        dp = [[0] * len(piles) for _ in range(len(piles))]
        for i in range(len(piles)):
            dp[i][i] = piles[i]
            
        for length in range(2, len(piles) + 1):
            for i in range(0, len(piles) - length + 1):
                j = i + length - 1
                dp[i][j] = max(piles[i] - dp[i + 1][j], piles[j] - dp[i][j - 1])
        
        return dp[0][len(piles) - 1]


class Solution:
    def stoneGame(self, piles: List[int]) -> bool:
        
        m = len(piles)
        dp = [[0 for _ in range(m)] for _ in range(m)]

        for i in range(m):
            dp[i][i] = piles[i]

        for length in range(2, m + 1):
            for start in range(0, m, 1):
                end = start + length - 1
                if end >= m:
                    break

                dp[start][end] = max(piles[start] - dp[start+1][end], piles[end] - dp[start][end-1])
        
        return dp[0][m - 1] > 0


from functools import lru_cache
class Solution:
    def stoneGame(self, piles):
        grid = [[0]*len(piles) for x in range(len(piles))]
        for i in range(len(piles)-1, -1, -1):
          for j in range(len(piles)):
            if i >= j: grid[i][j] = 0
            else:
              #alex
              if (j-i)%2 == 1:
                grid[i][j] = max(piles[i] + grid[i+1][j], piles[j] + grid[i][j-1])
              #lee
              else:
                grid[i][j] = min(-piles[i] + grid[i+1][j], -piles[j] + grid[i][j-1])
        return grid[0][len(piles)-1] > 0

class Solution:
    def stoneGame(self, piles: List[int]) -> bool:
        dp = [[(0,0)] * len(piles) for _ in range(len(piles))]
        for i in range(len(piles)):
            dp[i][i] = (piles[i], 0)
            
        for diff in range(1,len(piles)):
            for j in range(len(piles) - diff):
                i = diff + j
                left = dp[j+1][i][1] + piles[j]
                right = dp[j][i-1][1] + piles[i]
                if left > right:
                    dp[j][i] = (left, dp[j+1][i][0])
                else:
                    dp[j][i] = (right, dp[j][i-1][0])
        
        return dp[0][-1][0] > dp[0][-1][1]


class Solution:
    def stoneGame(self, piles: List[int]) -> bool:
        
        @lru_cache(None)
        def get_score(i, j):
            if i > j:
                return 0
            if i == j:
                return piles[i]
            return max(piles[i] + get_score(i + 2, j), piles[i] + get_score(i + 1, j - 1),
                      piles[j] + get_score(i + 1, j - 1), piles[j] + get_score(i, j - 2))
        
        return 2 * get_score(0, len(piles) - 1) > sum(piles)

class Solution:
    def stoneGame(self, piles: List[int]) -> bool:
        # use dp
        # answer the question \"what is the expected gain of the current player over the next player given the plies[i : j] (inclusive)\"
        table = [[0 for _ in range(len(piles))] for _ in range(len(piles))]
        
        # base case - single element
        for i in range(len(piles)):
            table[i][i] = piles[i]
        
        for diff in range(1, len(piles)):
            for i in range(0, len(piles) - diff):
                table[i][i + diff] = max(piles[i] - table[i + 1][i + diff], 
                                         piles[i + diff] - table[i][i + diff - 1])
        
        return table[0][len(piles) - 1] > 0

class Solution:
    def stoneGame(self, p: List[int]) -> bool:
        n = len(p)
        dp = [[0]*n for _ in range(n)]
        for i in range(n):
            dp[i][i] = p[i]
        for d in range(1, n):
            for i in range(n - d):
                # print(i, i+d)
                dp[i][i+d] = max(p[i]-dp[i+1][i+d], p[i+d]-dp[i][i+d-1])
        return dp[0][-1] > 0

class Solution:
    def stoneGame(self, piles):
        n = len(piles)
        dp = [[0 for _ in range(n)] for _ in range(n)]
        presum = [0]
        for p in piles:
            presum.append(p + presum[-1])

        for i in range(n):
            dp[i][i] = piles[i]
        for i in range(n - 1, -1, -1):
            for j in range(i + 1, n):
                dp[i][j] = max(piles[i] + presum[j + 1] - presum[i + 1] - dp[i + 1][j],
                               piles[j] + presum[j] - presum[i] - dp[i][j - 1])
        return dp[0][n - 1] > presum[-1] - dp[0][n - 1]

class Solution:
    def stoneGame(self, piles: List[int]) -> bool:
        n = len(piles)
        dp = [[0] * n for i in range(n)]

        for i in range(n):
            dp[i][i] = piles[i]
        
        for d in range(1, n + 1):
            for i in range(n - d):
                dp[i][i + d] = max(piles[i] - dp[i + 1][i + d], piles[i + d] - dp[i][i + d - 1])
        
        return dp[0][-1] > 0

class Solution:
    def stoneGame(self, piles: List[int]) -> bool:
        n = len(piles)
        dp = [[0] * n for _ in range(n)]
        for i in range(n): dp[i][i] = piles[i]
        cum = [0] * n
        cum[0] = piles[0]
        for i in range(1, n):
            cum[i] = cum[i-1] + piles[i]
        
        for l in range(1, n):
            for i in range(n - l):
                j = i + l
                dp[i][j] = max(piles[i] + cum[n-1] - dp[i+1][j], piles[j] + cum[n-1] - dp[i][j-1])
                
        return dp[0][n - 1] > (cum[n-1] // 2)

class Solution:
    def stoneGame(self, piles: List[int]) -> bool:
        # dp[i][j] represents the max difference in score current player gets over other player
        dp = [[0 for _ in range(len(piles))] for _ in range(len(piles))]
        
        # base case where length of list is 1
        for i in range(len(piles)):
            dp[i][i] = piles[i]
        
        start = len(piles) - 1
        while start >= 0:
            end = start + 1
            while end < len(piles):
                dp[start][end] = max(piles[start] - dp[start + 1][end], piles[end] - dp[start][end - 1])
                end += 1
            start -= 1
        
        return dp[0][len(piles) - 1] >= 0

class Solution:
    def stoneGame(self, piles: List[int]) -> bool:
        n = len(piles)    
        dp = [[0]*n for _ in range(n)]
        
        for i in range(n):
            dp[i][i] = piles[i]
            
        for i in range(n-1):
            for j in range(n):
                dp[i][j] = max(piles[i]-dp[i+1][j], piles[j] - dp[i][j - 1])
                
        
        return dp[0][n-1] > 0


class Solution:
    def stoneGame(self, piles: List[int]) -> bool:
        
        @lru_cache(None)
        def game(left, right):
            if left == right:
                return piles[left]
            return max(piles[left] - game(left + 1, right), piles[right] - game(left, right - 1))
        
        return game(0, len(piles) - 1) > 0

from functools import lru_cache
class Solution:
    def stoneGame(self, piles: List[int]) -> bool:
        # time complexity: O(n^2)
        # space complexity: O(n)
        @lru_cache(maxsize=None)
        def score(l, r):
            if l == r: return piles[l]
            return max(piles[l] - score(l+1, r),
                        piles[r] - score(l, r-1))
        return score(0, len(piles)-1) > 0

from functools import lru_cache
class Solution:
    def stoneGame(self, piles: List[int]) -> bool:
        @lru_cache(maxsize=None)
        def score(l, r):
            if l == r: return piles[l]
            return max(piles[l] - score(l+1, r),
                        piles[r] - score(l, r-1))
        return score(0, len(piles)-1) > 0

from functools import lru_cache
class Solution:
    def stoneGame(self, piles: List[int]) -> bool:
        memo = {}
        return self.dfs(0, 0, piles, 0, len(piles)-1, memo)
    
    def dfs(self, person1, person2, piles, start, end, memo):
        if (person1, person2, start, end) in memo:
            return memo[(person1, person2, start, end)]
        
        if end-start == 1:
            if person1 + max(piles) > person2 + min(piles):
                return True
            else:
                return False
        
        case1_person1 = person1 + piles[0]
        res1 = self.dfs(person2, case1_person1, piles, start+1, end, memo)
        if res1 == False:
            memo[(person1, person2, start, end)] = True
            return True
        
        case2_person1 = person1+piles[-1]
        res2 = self.dfs(person2, case2_person1, piles, start, end-1, memo)
        if res2 == False:
            memo[(person1, person2, start, end)] = True
            return True
        

        memo[(person1, person2, start, end)] = False
        
        return False
    


class Solution:
    # @lru_cache(None)
    def stoneGame(self, piles: List[int]) -> bool:
        result = dict()
        @lru_cache(None)
        def Alex(start, end) -> int:
            if start == end:
                return piles[start]
            # if (start, end) in result:
            #     return result[(start, end)]
            else:
                # result[(start, end)] = max(Lee(start + 1, end) + piles[start], Lee(start, end - 1) + piles[end])
                return max(Lee(start + 1, end) + piles[start], Lee(start, end - 1) + piles[end])
            # return result[(start, end)]
            
        def Lee(start, end) -> int:
            if start == end:
                return 0
            # if (start, end) in result:
            #     return result[(start, end)]
            else:
                # result[(start, end)] =  min(Alex(start + 1, end), Alex(start, end - 1))
                return  min(Alex(start + 1, end), Alex(start, end - 1))
            # return result[(start, end)]
        Alex(0, len(piles) - 1)
        summ = sum(piles)
        # print(result[(0, len(piles - 1))])
        # print(summ)
        return Alex(0, len(piles) - 1) > (summ - Alex(0, len(piles) - 1))

class Solution:
    def stoneGame(self, piles: List[int]) -> bool:
        memory = [[0 for _ in range(len(piles))]for _ in range(len(piles))]
        return self.dfs(piles, 0, len(piles)-1, True, memory) > 0
    def dfs(self, piles, start, end, turn, memory):
        if start > end:
            return 0
        if memory[start][end] != 0:
            return memory[start][end]
        if turn:
            memory[start][end] = max(piles[start] + self.dfs(piles, start+1, end, not turn, memory), piles[end] + self.dfs(piles, start, end-1, not turn, memory))
        else:
            memory[start][end] =  min(-piles[start] + self.dfs(piles, start+1, end, not turn, memory), -piles[end] + self.dfs(piles, start, end-1, not turn, memory))
        return memory[start][end]
        


from functools import lru_cache

class Solution:
    def stoneGame(self, piles: List[int]) -> bool:
        @lru_cache(None)
        def helper(l,r):
            if r-l == 1:
                return piles[l]
            if r-l == 2:
                return abs(piles[l] - piles[l+1])
            return max(piles[l] - helper(l+1, r), piles[r-1] - helper(l,r-1))
            
        return helper(0,len(piles)) > 0

class Solution:
    def stoneGame(self, piles: List[int]) -> bool:
        n=len(piles)
        if n//2==0:
            return True
        dp=[[0 for i in range(n)] for j in range(n)]
        prefix=[0]
        for i in range(n):
            dp[i][i]=piles[i]
            prefix.append(prefix[-1]+piles[i])
        for k in range(1,n):
            for i in range(n):
                j=i+k
                if j>=n:
                    break
                dp[i][j]=piles[j]+((prefix[j]-prefix[i])-dp[i][j-1])
                dp[i][j]=max(dp[i][j],piles[i]+((prefix[j+1]-prefix[i+1])-dp[i+1][j]))
        return (dp[0][-1]>sum(piles)//2)