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: MEDIUM
Tags: Dynamic programming

Data structures

Game theory

Mathematics
Skill types: Dynamic programming

Data structures

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


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):
		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(object):

	def stoneGame(self, piles):
		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


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):
				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)

		@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:
		n = len(piles)
		dp = [[0] * n for i in range(n)]
		for d in range(1, n):
			for i in range(n - d):
				j = i + 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]))
		return dp[0][n - 1] > sum(piles) - dp[0][n - 1]


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]))
		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:

	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)
		return result[0, len(piles) - 1] > summ - result[0, len(piles) - 1]


class Solution:

	def stoneGame(self, piles: List[int]) -> bool:
		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:
				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:
		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
			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))
		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:
		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]


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):
			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
		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:

		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]
		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


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:
		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]
			elif 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


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):
		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:
				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):
				j = i + alen - 1
				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))
			memo[i, j] = ans
			return ans
		return dp(0, n - 1) > 0

	def stoneGame4(self, piles):
		return True

	def stoneGame3(self, piles):
		n = len(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):
		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):
				j = i + alen - 1
				dp[i][j] = max(piles[i] - dp[i + 1][j], piles[j] - dp[i][j - 1])
		return dp[0][n - 1] > 0

	def stoneGame1(self, piles: List[int]) -> bool:
		dp = dict()

		def score(piles, l, r):
			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))
			dp[l, r] = res
			return res
		res = score(piles, 0, len(piles) - 1)
		return True if res > 0 else False


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


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:
		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


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]


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))]
		for i in range(len(piles)):
			dp[i][i] = [piles[i], 0]
		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):
			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))

		@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


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]
		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:

	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


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


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):
				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)
		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):
		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)
		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]


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:
		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:
		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:
		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, 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:
		n = len(piles)
		if n == 1:
			return True
		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:
		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


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, 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:
		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, 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:
		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
				elif (j - i) % 2 == 1:
					grid[i][j] = max(piles[i] + grid[i + 1][j], piles[j] + grid[i][j - 1])
				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:

		@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:
		table = [[0 for _ in range(len(piles))] for _ in range(len(piles))]
		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, 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:
		dp = [[0 for _ in range(len(piles))] for _ in range(len(piles))]
		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:

		@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:

		@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:

	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