Given an array of scores that are non-negative integers. Player 1 picks one of the numbers from either end of the array followed by the player 2 and then player 1 and so on. Each time a player picks a number, that number will not be available for the next player. This continues until all the scores have been chosen. The player with the maximum score wins. 

Given an array of scores, predict whether player 1 is the winner. You can assume each player plays to maximize his score. 

Example 1:

Input: [1, 5, 2]
Output: False
Explanation: Initially, player 1 can choose between 1 and 2. If he chooses 2 (or 1), then player 2 can choose from 1 (or 2) and 5. If player 2 chooses 5, then player 1 will be left with 1 (or 2). So, final score of player 1 is 1 + 2 = 3, and player 2 is 5. Hence, player 1 will never be the winner and you need to return False.



Example 2:

Input: [1, 5, 233, 7]
Output: True
Explanation: Player 1 first chooses 1. Then player 2 have to choose between 5 and 7. No matter which number player 2 choose, player 1 can choose 233.Finally, player 1 has more score (234) than player 2 (12), so you need to return True representing player1 can win.



Note:

1 
Any scores in the given array are non-negative integers and will not exceed 10,000,000.
If the scores of both players are equal, then player 1 is still the winner.

Difficulty: interview

Starter code:

class Solution:
    def PredictTheWinner(self, nums: List[int]) -> bool:
        

Solutions:
class Solution:
     def PredictTheWinner(self, nums):
         """
         :type nums: List[int]
         :rtype: bool
         """
         if not nums: return True
         n = len(nums)
         if n & 1 == 0: return True
         
         dp = [0] * n
         for i in range(n-1, -1, -1):
             for j in range(i, n):
                 if i == j:
                     dp[i] = nums[i]
                 else:
                     dp[j] = max(nums[i] - dp[j], nums[j] - dp[j-1])
         return dp[n-1] >= 0


class Solution:
     def PredictTheWinner(self, nums):
         """
         :type nums: List[int]
         :rtype: bool
         """
         # total = sum(nums)
         # memo = {}
         # def score(l, r, t):
         #     if l>r: return 0
         #     if (l, r) not in memo:
         #         memo[(l, r)] = t-min(score(l+1, r, t-nums[l]), score(l, r-1, t-nums[r]))
         #     return memo[(l, r)]
         # sc = score(0, len(nums)-1, total)
         # return sc>=total-sc
         N = len(nums)
         dp = [[0]*N for _ in range(N)]
         pre_sum = [nums[0]]*(N+1)
         pre_sum[-1] = 0
         for i in range(1, N):
             pre_sum[i] = pre_sum[i-1]+nums[i]
         for i in range(N):
             dp[i][i] = nums[i]
         for l in range(1, N):
             for i in range(N-l):
                 dp[i][i+l] = max(pre_sum[i+l]-pre_sum[i-1]-dp[i+1][i+l], pre_sum[i+l]-pre_sum[i-1]-dp[i][i+l-1])
         return dp[0][N-1]*2>=pre_sum[N-1]

class Solution:
     def PredictTheWinner(self, nums):
         cache = {}
         
         def whose_turn(i, j):
             return (len(nums) - (j - i + 1)) % 2 == 0
         
         def traverse(i, j):
             if (i, j) in cache:
                 return cache[(i, j)]
             
             p1_turn = whose_turn(i, j)
             
             if i == j:
                 return (nums[i], 0) if p1_turn else (0, nums[i])
                  
             if i + 1 == j:
                 winning_move = max(nums[i], nums[j])
                 losing_move = min(nums[i], nums[j])
                 cache[(i, j)] = (winning_move, losing_move) if p1_turn else (losing_move, winning_move)
                 return cache[(i, j)]
                 
             p1_left, p2_left = traverse(i + 1, j)
             p1_right, p2_right = traverse(i, j - 1)
             
             if p1_turn:
                 p1_move = max(p1_left + nums[i], p1_right + nums[j])
                 p2_move = p2_left if p1_left + nums[i] >= p1_right + nums[j] else p2_right
             else:
                 p1_move = p1_left if p2_left + nums[i] >= p2_right + nums[j] else p1_right
                 p2_move = max(p2_left + nums[i], p2_right + nums[j])
             
             cache[(i, j)] = (p1_move, p2_move)
             return cache[(i, j)]
         
         p1_final, p2_final = traverse(0, len(nums) - 1)
         return p1_final >= p2_final

class Solution:
     def PredictTheWinner(self, nums):
         """
         :type nums: List[int]
         :rtype: bool
         
         """
         memo = [ [0 for _ in range(len(nums))] for _ in range(len(nums))]
         self.count=0
         
         def winner( left , right , player):
             self.count +=1
             #print(self.count)
             if left == right:
                 
                 return player * nums[left]
            
             # p1 selct max from each end
             # remove the selected
             # p2 selects max from each end
             # do above seps until no mor num
             # 1 5 2
             #print( left, right)
             
             if memo[left][right] != 0 :
                 print((nums[left:right+1]))
                 return memo[left][right]
            
             #self.count +=1
             a = player * nums[left] + winner( left+1 , right, -player )
             
             #self.count +=1
             b = player * nums[right] + winner( left , right -1 , -player)
             
             
             
             if player == 1:
                 res = max(a,b)
             else:
                 res = min(a,b)
                 
             memo[left][right] = res
             
             return res
             
         self.count=0    
         return winner( 0, len(nums) -1 , 1) >=0 
         
             
                 
         


class Solution:
     def PredictTheWinner(self, nums):
         """
         :type nums: List[int]
         :rtype: bool
         """
         n = len(nums)
         if n == 0:
             return False
         dp = [[0]*n for i in range(n)]
         for i in range(n):
             dp[i][i] = nums[i]
         for period in range(1,n): 
             for i in range(n-period):
                 j = i+period
                 dp[i][j] = max(nums[i]-dp[i+1][j], nums[j]-dp[i][j-1])
         return dp[0][n-1] >= 0


class Solution:
     def PredictTheWinner(self, nums):
         """
         :type nums: List[int]
         :rtype: bool
         """
         def helper(nums, start, end, mem):
             if start == end:
                 return nums[start]
             if (start, end) not in mem:
                 mem[(start, end)] = max(nums[start] - helper(nums, start + 1, end, mem), nums[end] - helper(nums, start, end - 1, mem))
             return mem[(start, end)]
         
         return helper(nums, 0, len(nums) - 1, {}) >= 0

class Solution:
     def PredictTheWinner(self, nums):
         """
         :type nums: List[int]
         :rtype: bool
         """
         dic = {}
         # tnums = tuple(nums)
         # move to the solve function
         def solve(nums):
             ###BUG！ IndexError: list index out of range
             if len(nums) <=1: return sum(nums)
             tnums = tuple(nums)
             if tnums in dic:
                 return dic[tnums]
             dic[tnums] = max(nums[0]-solve(nums[1:]),nums[-1]-solve(nums[:-1]))
             # TypeError: unsupported operand type(s) for -: 'int' and 'NoneType'
             return dic[tnums]
         return solve(nums) >= 0

class Solution:
     def PredictTheWinner(self, nums):
         """
         :type nums: List[int]
         :rtype: bool
         """
         total = sum(nums)
         dic = {}
         def score(i, j, t):
             if i>j:
                 return 0
             if (i, j) in dic:
                 return dic[(i, j)]
             ret = max(t-score(i+1, j, t-nums[i]), t-score(i, j-1, t-nums[j]))
             dic[(i, j)] = ret
             return ret
         l = len(nums)
         sc = score(0, l-1, total)
         return sc>=total-sc

class Solution:
     def PredictTheWinner(self, nums):
         """
         :type nums: List[int]
         :rtype: bool
         """
         if not nums:
             return 0
         n=len(nums)
         dp=[[0]*n for _ in range(n)]
         
         for i in range(n):
             dp[i][i]=nums[i]
             
         for length in range(1,n):
             for i in range(n-length):
                 j=i+length
                 dp[i][j]=max(nums[i]-dp[i+1][j],nums[j]-dp[i][j-1])
                 
         return dp[0][-1]>=0


class Solution:
     p1dict = {}
     p2dict = {}
     
     def play1(self, nums):
         if str(nums) in self.p1dict:
             return self.p1dict[str(nums)]
         if len(nums) == 1:
             return nums[0]
         ret = max(self.play2(nums[1:]) + nums[0], self.play2(nums[:-1]) + nums[-1])
         self.p1dict[str(nums)] = ret
         return ret
     
     def play2(self, nums):
         if str(nums) in self.p2dict:
             return self.p2dict[str(nums)]
         if len(nums) == 1:
             return -nums[0]
         ret = min(self.play1(nums[1:]) - nums[0], self.play1(nums[:-1]) - nums[-1])
         self.p2dict[str(nums)] = ret
         return ret
     
     def PredictTheWinner(self, nums):
         """
         :type nums: List[int]
         :rtype: bool
         """
         return self.play1(nums) >= 0


class Solution:
     def PredictTheWinner(self, nums):
         """
         :type nums: List[int]
         :rtype: bool
         """
         _cache = {}
         return Solution.Moves(self,nums, 0,len(nums)-1, 1, _cache ) >= 0
         
     
     def Moves(self, nums, ini ,fin, pl, _cache = {}):
         
         memo = str((ini,fin,pl))
         
         if memo in list(_cache.keys()):
             return _cache[memo]
           
         if ini == fin :
             if pl == 1:
                 _cache[memo] = nums[ini]
                 return _cache[memo]
             else:
                 _cache[memo] = - nums[ini]
                 return _cache[memo]
         else:
             if pl == 1:             
                 _cache[memo]= max(Solution.Moves(self, nums, ini+1, fin, 2,_cache) + nums[ini] , Solution.Moves(self, nums, ini, fin-1, 2,_cache) + nums[fin])
                 return _cache[memo]
             
             if pl == 2:
                 _cache[memo] = min(Solution.Moves(self, nums, ini+1, fin, 1,_cache) - nums[ini] , Solution.Moves(self, nums, ini, fin-1, 1,_cache) - nums[fin])
                 return _cache[memo]


class Solution:
     def PredictTheWinner(self, nums):
         """
         :type nums: List[int]
         :rtype: bool
         """
         l = len(nums)
         memo = [[None] * l for _ in range(l)]
         def predict(start, end, memo):
             if start == end:
                 return nums[start]
             if memo[start][end]:
                 return memo[start][end]
             one = nums[start] - predict(start + 1, end, memo)
             two = nums[end] - predict(start, end - 1, memo)
             memo[start][end] = max(one, two)
             return memo[start][end]
         
         return predict(0, len(nums) - 1, memo) >= 0

class Solution:
     def PredictTheWinner(self, nums):
         """
         :type nums: List[int]
         :rtype: bool
         """
         if not nums: return True
         n = len(nums)
         if n & 1 == 0: return True
         
         dp = [0] * n
         for i in range(n-1, -1, -1):
             for j in range(i, n):
                 if i == j:
                     dp[i] = nums[i]
                 else:
                     dp[j] = max(nums[i] - dp[j], nums[j] - dp[j-1])
         return dp[n-1] >= 0