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

 
Constraints:

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

Source: leetcode | Difficulty: MEDIUM
Tags: Dynamic programming

Data structures

Game theory

Mathematics

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

Solutions:
from functools import *

class Solution:

	def stoneGameII(self, arr):
		a = []
		s = 0
		n = len(arr)
		for i in arr[::-1]:
			s += i
			a.append(s)
		a = a[::-1]

		@lru_cache(None)
		def fun(i, m):
			if i + 2 * m >= n:
				return a[i]
			mn = inf
			for ii in range(1, 2 * m + 1):
				if ii > m:
					ans = fun(i + ii, ii)
				else:
					ans = fun(i + ii, m)
				if ans < mn:
					mn = ans
			return a[i] - mn
		return fun(0, 1)


from functools import lru_cache

class Solution:

	def stoneGameII(self, piles: List[int]) -> int:
		N = len(piles)
		for i in range(N - 2, -1, -1):
			piles[i] += piles[i + 1]

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


class Solution:

	def stoneGameII(self, piles: List[int]) -> int:
		for i in range(len(piles) - 2, -1, -1):
			piles[i] += piles[i + 1]
		memo = {}

		def dfs(i, m):
			if i + 2 * m >= len(piles):
				return piles[i]
			if (i, m) in memo:
				return memo[i, m]
			memo[i, m] = piles[i] - min((dfs(i + j, max(m, j)) for j in range(1, 2 * m + 1)))
			return memo[i, m]
		return dfs(0, 1)


class Solution:

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


class Solution:

	def stoneGameII(self, piles: List[int]) -> int:
		for i in range(len(piles) - 2, -1, -1):
			piles[i] += piles[i + 1]
		from functools import lru_cache

		@lru_cache(None)
		def dp(index, m):
			if index >= len(piles):
				return 0
			max_val = 0
			for i in range(index, min(index + 2 * m, len(piles))):
				new_m = max(m, i + 1 - index)
				max_val = max(max_val, piles[index] - dp(i + 1, new_m))
			return max_val
		return dp(0, 1)
		max_num = 0

		def play(i, m, player):
			if i >= len(piles):
				return 0
			if player == 1:
				point = play(i + 2 * m, 2 * m, 0)
				return point
			else:
				max_point = 0
				for action in range(i + 1, min(i + 1 + 2 * m, len(piles))):
					print((sum(piles[i:action]), i, m, action, piles[i:action], min(i + 1 + 2 * m, len(piles))))
					down_stream_point = play(action, max(action, m), 1)
					max_point = max(max_point, sum(piles[i:action]) + down_stream_point)
				return max_point
		return play(0, 1, 0)


class Solution:

	def stoneGameII(self, piles: List[int]) -> int:
		N = len(piles)
		cache = {}

		def recursive_game(start, M):
			score_left = sum(piles[start:])
			if start >= N:
				return 0
			if (start, M) in cache:
				return cache[start, M]
			if start + 2 * M >= N:
				return score_left
			my_score = 0
			for x in range(1, 2 * M + 1):
				opponent_score = recursive_game(start + x, max(M, x))
				my_score = max(my_score, score_left - opponent_score)
			cache[start, M] = my_score
			return my_score
		return recursive_game(0, 1)


class Solution:

	def stoneGameII(self, piles: List[int]) -> int:
		from functools import lru_cache

		@lru_cache(None)
		def select(start, M, my_turn):
			if my_turn:
				if start + 2 * M >= len(piles):
					return sum(piles[start:])
				rst = 0
				for i in range(1, 2 * M + 1):
					rst = max(rst, sum(piles[start:start + i]) + select(start + i, max(i, M), False))
				return rst
			if start + 2 * M >= len(piles):
				return 0
			rst = float('inf')
			for i in range(1, 2 * M + 1):
				rst = min(rst, select(start + i, max(i, M), True))
			return rst
		return select(0, 1, True)


class Solution:

	def stoneGameII(self, A: List[int]) -> int:
		seen = {}

		def max_stones(sidx, m):
			if sidx == len(A):
				return 0
			if (sidx, m) not in seen:
				if len(A) - sidx <= 2 * m:
					seen[sidx, m] = sum(A[sidx:])
				else:
					res = 0
					for x in range(1, 2 * m + 1):
						new_sidx = sidx + x
						res = max(res, sum(A[sidx:]) - max_stones(new_sidx, max(m, x)))
					seen[sidx, m] = res
			return seen[sidx, m]
		return max_stones(0, 1)


class Solution:

	def stoneGameII(self, piles: List[int]) -> int:
		table = {}

		def stoneGameRec(start, M):
			if (start, M) in table:
				return table[start, M]
			totalTaken = 0
			for i in range(start, min(start + 2 * M, len(piles))):
				totalTaken += piles[i]
			if start + 2 * M >= len(piles):
				return (totalTaken, 0)
			maxStones = (0, 0)
			for i in range(start + 2 * M - 1, start - 1, -1):
				X = i - start + 1
				(theirStones, yourStones) = stoneGameRec(i + 1, max(M, X))
				yourStones += totalTaken
				if yourStones > maxStones[0]:
					maxStones = (yourStones, theirStones)
				totalTaken -= piles[i]
			table[start, M] = maxStones
			return maxStones
		(alexScore, _) = stoneGameRec(0, 1)
		return alexScore


class Solution:

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

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


class Solution:

	def stoneGameII(self, piles: List[int]) -> int:
		n = len(piles)
		dp = [[0 for m in range(n)] for i in range(n)]
		sufsum = [0] * (n + 1)
		for i in reversed(range(n)):
			sufsum[i] = sufsum[i + 1] + piles[i]
		return self.dfs(piles, 0, dp, sufsum, 1)

	def dfs(self, piles, index, dp, sufsum, M):
		if index == len(piles):
			return 0
		if dp[index][M] > 0:
			return dp[index][M]
		result = 0
		for i in range(index, index + 2 * M):
			if i >= len(piles):
				break
			X = i - index + 1
			result = max(result, sufsum[index] - self.dfs(piles, i + 1, dp, sufsum, max(X, M)))
		dp[index][M] = result
		return dp[index][M]


import functools

class Solution:

	def stoneGameII(self, piles: List[int]) -> int:
		n = len(piles)
		for i in range(n - 2, -1, -1):
			piles[i] += piles[i + 1]

		@lru_cache(None)
		def dp(i, m):
			if i + 2 * m >= n:
				return piles[i]
			res = 0
			for x in range(1, 2 * m + 1):
				res = max(res, piles[i] - dp(i + x, max(m, x)))
			return res
		return dp(0, 1)


class Solution:

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


class Solution:

	def stoneGameII(self, piles: List[int]) -> int:
		mem = {}

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


class Solution:

	def stoneGameII(self, piles: List[int]) -> int:
		n = len(piles)
		dp = [[-1 for _ in range(n + 1)] for _ in range(n + 1)]
		s = sum(piles)

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


class Solution:

	def stoneGameII(self, piles: List[int]) -> int:
		n = len(piles)
		s = sum(piles[:])
		memo = [[-sys.maxsize for i in range(2 * n)] for j in range(n)]

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


class Solution:

	def stoneGameII(self, piles: List[int]) -> int:
		n = len(piles)
		post = [0] * (n + 1)
		for i in range(n - 1, -1, -1):
			post[i] = post[i + 1] + piles[i]
		dp = [[-1] * 200 for _ in range(101)]

		def solve(i, m):
			if i >= len(piles):
				return 0
			if dp[i][m] > 0:
				return dp[i][m]
			s = ans = 0
			for di in range(1, 2 * m + 1):
				ii = i + di - 1
				if ii >= len(piles):
					break
				s += piles[ii]
				other = solve(ii + 1, max(m, di))
				ans = max(ans, s + post[ii + 1] - other)
			dp[i][m] = ans
			return ans
		return solve(0, 1)


class Solution:

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

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


class Solution:

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

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


class Solution:

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

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


class Solution:

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

		@lru_cache(None)
		def dp1(prev, m):
			if prev >= n - 1:
				return 0
			maxcount = 0
			for x in range(1, m * 2 + 1):
				if prev + x >= n:
					break
				ret = dp2(prev + x, max(m, x))
				maxcount = max(maxcount, ret + sum(piles[prev + 1:prev + x + 1]))
			return maxcount

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


class Solution:

	def stoneGameII(self, piles: List[int]) -> int:
		(A, n) = (piles, len(piles))
		for i in range(n - 2, -1, -1):
			A[i] += A[i + 1]

		@lru_cache(maxsize=None)
		def helper(i, m):
			if i + 2 * m >= len(piles):
				return A[i]
			res = 0
			for x in range(1, 2 * m + 1):
				res = max(res, A[i] - helper(i + x, max(m, x)))
			return res
		return helper(0, 1)


import math
from functools import lru_cache

class Solution:

	def stoneGameII(self, piles: List[int]) -> int:
		solved = {}
		ps = [0] + piles[:]
		for i in range(1, len(ps)):
			ps[i] += ps[i - 1]

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


class Solution:

	def stoneGameII(self, piles: List[int]) -> int:
		l = len(piles)
		self.len = l
		dp = {}
		total = sum(piles)
		maxDiff = self.help(piles, 0, 1, dp)
		return int((total + maxDiff) / 2)

	def help(self, piles, index, m, dp):
		if index >= self.len:
			return 0
		if dp.get((index, m)) != None:
			return dp.get((index, m))
		res = -268435455
		s = 0
		for i in range(index, self.len):
			if i - 2 * m >= index:
				break
			s += piles[i]
			res = max(res, s - self.help(piles, i + 1, max(m, i - index + 1), dp))
		dp[index, m] = res
		return res


import numpy as np
from functools import lru_cache

class Solution:

	def stoneGameII(self, piles: List[int]) -> int:
		cumsum = np.cumsum(piles[::-1])

		@lru_cache(None)
		def optimalValue(m, s):
			if s == 0:
				return 0
			cumsum[s - 1]
			return max([cumsum[s - 1] - optimalValue(max(m, n), s - n) for n in range(1, 2 * m + 1) if s - n >= 0])
		return optimalValue(1, len(piles))


from functools import lru_cache

class Solution:

	def stoneGameII(self, a: List[int]) -> int:
		n = len(a)
		sums = [0] * n
		sums[-1] = a[-1]
		for i in reversed(range(len(sums) - 1)):
			sums[i] = a[i] + sums[i + 1]

		@lru_cache(None)
		def dp(i, m):
			if i >= n:
				return 0
			return max((sums[i] - dp(i + x, max(x, m)) for x in range(1, 2 * m + 1)))
		return dp(0, 1)


MIN = float('-inf')

class Solution:

	def stoneGameII(self, piles):
		n = len(piles)
		preSum = [0] * (n + 1)
		for i in range(1, n + 1):
			preSum[i] += preSum[i - 1] + piles[i - 1]

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


from functools import lru_cache

class Solution:

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

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


class Solution:

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

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


class Solution:

	def stoneGameII(self, piles: List[int]) -> int:
		n = len(piles)
		prefix_sum = [0] * (n + 1)
		for i in range(1, len(prefix_sum)):
			prefix_sum[i] = prefix_sum[i - 1] + piles[i - 1]
		memo = {}

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


class Solution:

	def helper(self, s, M, n):
		if s >= n:
			return 0
		if (s, M) in self.mem:
			return self.mem[s, M]
		(cur, best) = (0, -float('inf'))
		for x in range(1, 2 * M + 1):
			if s + x > n:
				break
			cur += self.piles[s + x - 1]
			best = max(best, cur - self.helper(s + x, max(x, M), n))
		self.mem[s, M] = best
		return best

	def stoneGameII(self, piles: List[int]) -> int:
		n = len(piles)
		self.mem = {}
		self.piles = piles
		return (sum(piles) + self.helper(0, 1, n)) // 2


class Solution:

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

		@lru_cache(None)
		def minimax(start, m, player):
			if start >= len(piles):
				return 0
			if player == 1:
				return max((sum(piles[start:start + x]) + minimax(start + x, max(x, m), 2) for x in range(1, 2 * m + 1)))
			if player == 2:
				return min((minimax(start + x, max(x, m), 1) for x in range(1, 2 * m + 1)))
		return minimax(0, 1, 1)


class Solution:

	def stoneGameII(self, piles: List[int]) -> int:
		length = len(piles)
		dp = [[0] * length for i in range(length)]
		visited = [[0] * (length + 1) for i in range(length + 1)]

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


class Solution:

	def stoneGameII(self, piles: List[int]) -> int:
		for i in range(len(piles) - 2, -1, -1):
			piles[i] += +piles[i + 1]
		from functools import lru_cache

		@lru_cache(None)
		def takeStone(startInd, M):
			if startInd + 2 * M >= len(piles):
				return piles[startInd]
			bestChoice = float('inf')
			for X in range(1, 2 * M + 1):
				newInd = startInd + X
				bestChoice = min(bestChoice, takeStone(newInd, max(X, M)))
			return piles[startInd] - bestChoice
		return takeStone(0, 1)


class Solution:

	def stoneGameII(self, piles: List[int]) -> int:
		p = [0]
		cur = 0
		for i in piles:
			cur += i
			p.append(cur)
		n = len(piles)
		from functools import lru_cache

		@lru_cache(None)
		def dp(start, m):
			if start >= n:
				return 0
			return max((p[-1] - p[start] - dp(start + i, max(i, m)) for i in range(1, 2 * m + 1)))
		return dp(0, 1)


class Solution:

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

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


class Solution:

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

		@lru_cache(maxsize=None)
		def helper(i, j, M, turn=True):
			if i >= j:
				return 0
			X = list(range(1, 2 * M + 1))
			if turn:
				maxalex = -sys.maxsize
			else:
				maxalex = sys.maxsize
			for x in X:
				if turn:
					if i + x <= j:
						alex = sum(self.piles[i:i + x]) + helper(i + x, j, max(x, M), turn=False)
						maxalex = max(alex, maxalex)
				else:
					alex = helper(i + x, j, max(x, M), turn=True)
					maxalex = min(alex, maxalex)
			return maxalex
		return helper(0, len(self.piles), 1)


class Solution:

	def stoneGameII(self, piles: List[int]) -> int:
		result = dict()
		result_min = dict()

		def minimax(start, M, player):
			if start >= len(piles):
				return 0
			if player == 1:
				if (start, M) in result:
					return result[start, M]
				maxnum = -1
				for X in range(1, 2 * M + 1):
					temp = minimax(start + X, max(X, M), 2) + sum(piles[start:start + X])
					if temp > maxnum:
						maxnum = temp
				result[start, M] = maxnum
				return maxnum
			if player == 2:
				minnum = 10 ^ 5
				if (start, M) in result_min:
					return result_min[start, M]
				minnum = 1000000
				for X in range(1, 2 * M + 1):
					temp = minimax(start + X, max(X, M), 1)
					if temp < minnum:
						minnum = temp
				result_min[start, M] = minnum
				return minnum
		res = minimax(0, 1, 1)
		print(result)
		print(result_min)
		return res


from functools import lru_cache

class Solution:

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

		@lru_cache(maxsize=None)
		def dfs(index, M):
			if 2 * M >= n - index:
				return sum(piles[index:])
			ret = float('inf')
			for X in range(1, 2 * M + 1):
				if X > n - index:
					break
				ret = min(ret, dfs(index + X, max(X, M)))
			return sum(piles[index:]) - ret
		return dfs(0, 1)


class Solution:

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

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

	def stoneGameII(self, piles: List[int]) -> int:
		lookup = {}

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


class Solution:

	def stoneGameII(self, piles: List[int]) -> int:
		s = 0
		for i in range(len(piles) - 1, -1, -1):
			s += piles[i]
			piles[i] = s

		def bt(m, player, M, remain, spiles):
			if remain <= 0:
				return 0
			key = (player, M, remain)
			if key in m:
				return m[key]
			res = 0
			for take in range(1, 2 * M + 1):
				index = len(piles) - remain
				res = max(res, spiles[index] - bt(m, 1 - player, max(M, take), remain - take, spiles))
			m[key] = res
			return res
		return bt({}, 0, 1, len(piles), piles)


class Solution:

	def stoneGameII(self, A: List[int]) -> int:
		n = len(A)
		memo = {}

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


class Solution:

	def stoneGameII(self, piles: List[int]) -> int:
		l = len(piles)
		dp = [[[-1 for i in range(l)] for j in range(2 * l)] for k in range(2)]

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


class Solution:

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

		def pick_stones(i, m, t):
			if i >= len(piles):
				return 0
			if (i, m, t) in d:
				return d[i, m, t]
			if t:
				d[i, m, t] = max((pick_stones(i + k, max(m, k), False) + sum(piles[i:i + k]) for k in range(1, 2 * m + 1)))
			else:
				d[i, m, t] = min((pick_stones(i + k, max(m, k), True) for k in range(1, 2 * m + 1)))
			return d[i, m, t]
		d = {}
		return pick_stones(0, 1, True)


class Solution:

	def playerGame(self, pos, piles, player1, M, memo):
		optionsCount = min(len(piles) - pos, 2 * M)
		resultPlayer1 = 0
		resultPlayer2 = 0
		for i in range(pos, pos + optionsCount):
			X = i - pos + 1
			stonesCount = 0
			for j in range(pos, i + 1):
				stonesCount += piles[j]
			combination = (i + 1, not player1, max(M, X))
			if combination in memo:
				(count1, count2) = memo[combination]
			else:
				(count1, count2) = self.playerGame(i + 1, piles, not player1, max(M, X), memo)
				memo[combination] = [count1, count2]
			if player1:
				if stonesCount + count1 > resultPlayer1:
					resultPlayer1 = stonesCount + count1
					resultPlayer2 = count2
			elif stonesCount + count2 > resultPlayer2:
				resultPlayer1 = count1
				resultPlayer2 = stonesCount + count2
		return (resultPlayer1, resultPlayer2)

	def stoneGameII(self, piles: List[int]) -> int:
		M = 1
		player1 = True
		memo = {}
		pos = 0
		return self.playerGame(pos, piles, player1, M, memo)[0]


class Solution:

	def stoneGameII(self, piles: List[int]) -> int:
		memo = {}
		n = len(piles)

		def dfs(player, start, m):
			if (player, start, m) in memo:
				return memo[player, start, m]
			cur = 0
			res = 0
			aj = i = start
			am = m
			while i < n and i - start + 1 <= 2 * m:
				cur += piles[i]
				(_, bj, bm) = dfs(1 - player, i + 1, max(i - start + 1, m))
				if res < cur + dfs(player, bj + 1, bm)[0]:
					res = cur + memo[player, bj + 1, bm][0]
					aj = i
					am = max(i - start + 1, m)
				i += 1
			memo[player, start, m] = (res, aj, am)
			return (res, aj, am)
		return dfs(0, 0, 1)[0]


class Solution:

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

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


class Solution:

	def stoneGameII(self, a: List[int]) -> int:

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


class Solution:

	def stoneGameII(self, piles: List[int]) -> int:
		self.arr = piles
		self.dp = {}
		ans = self.helper(0, 1, 1)
		print(self.dp)
		return ans

	def helper(self, i, m, turn):
		if i >= len(self.arr):
			return 0
		if (i, m, turn) in self.dp:
			return self.dp[i, m, turn]
		if turn:
			ans = []
			for x in range(2 * m):
				tmp = sum(self.arr[i:i + x + 1]) + self.helper(i + x + 1, max(x + 1, m), 0)
				ans.append(tmp)
			self.dp[i, m, turn] = max(ans)
			return self.dp[i, m, turn]
		else:
			ans = []
			for x in range(2 * m):
				tmp = self.helper(i + x + 1, max(x + 1, m), 1)
				ans.append(tmp)
			self.dp[i, m, turn] = min(ans)
			return self.dp[i, m, turn]


class Solution:

	def stoneGameII(self, piles: List[int]) -> int:
		if len(piles) == 1:
			return piles[0]
		pileCount = len(piles)
		scores = [[0 for y in range(0, len(piles))] for x in range(0, len(piles))]
		for i in range(len(scores) - 1, -1, -1):
			for M in range(1, len(scores[i])):
				if i + 2 * M >= pileCount:
					scores[i][M] = sum(piles[i:])
				else:
					m_options = [sum(piles[i:i + m]) + sum(piles[i + m:]) - scores[0 if i + m > pileCount else i + m][max(m, M)] for m in range(1, 2 * M + 1)]
					scores[i][M] = max(m_options)
		return scores[0][1]


class Solution:

	def stoneGameII(self, piles: List[int]) -> int:
		presum = list(piles)
		for i in range(1, len(piles)):
			presum[i] += presum[i - 1]
		from functools import lru_cache

		@lru_cache(None)
		def dp(ind, m):
			if ind + 2 * m >= len(piles):
				return presum[-1] - (presum[ind - 1] if ind > 0 else 0)
			sm = float('-inf')
			for i in range(1, 2 * m + 1):
				me = presum[ind + i - 1] - (presum[ind - 1] if ind > 0 else 0)
				sm = max(sm, me + presum[-1] - presum[ind + i - 1] - dp(ind + i, max(m, i)))
			return sm
		return dp(0, 1)


class Solution:

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


class Solution:

	@staticmethod
	def _suffix_sum(piles: List[int]) -> List[int]:
		suffix_sum = [0]
		for pile in reversed(piles):
			suffix_sum.append(suffix_sum[-1] + pile)
		suffix_sum.reverse()
		return suffix_sum

	def stoneGameII(self, piles: List[int]) -> int:
		suffix_sum = self._suffix_sum(piles)
		dp = [[0] * (len(piles) + 1) for _ in range(len(piles) + 1)]
		for pile in reversed(range(len(piles))):
			for M in reversed(range(len(piles))):
				sum_next_player = suffix_sum[pile]
				for next_pile in range(pile + 1, min(pile + 2 * M + 1, len(piles) + 1)):
					sum_next_player = min(sum_next_player, dp[next_pile][max(M, next_pile - pile)])
				sum_player = suffix_sum[pile] - sum_next_player
				dp[pile][M] = sum_player
		return dp[0][1]


class Solution:

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


class Solution:

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

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


class Solution:

	def solve(self, start, end, M, player):
		if (start, end, M, player) in self.dp:
			return self.dp[start, end, M, player]
		maxa = 0
		maxl = 0
		if start > end:
			return [0, 0]
		for i in range(1, 2 * M + 1):
			picked = sum(self.piles[start:start + i])
			if player == 0:
				(a, l) = self.solve(start + i, end, max(i, M), 1)
				if picked + a > maxa:
					maxa = picked + a
					maxl = l
			else:
				(a, l) = self.solve(start + i, end, max(i, M), 0)
				if picked + l > maxl:
					maxa = a
					maxl = picked + l
		self.dp[start, end, M, player] = (maxa, maxl)
		return (maxa, maxl)

	def stoneGameII(self, piles: List[int]) -> int:
		self.dp = {}
		self.piles = piles
		ans = self.solve(0, len(piles) - 1, 1, 0)
		print(self.dp)
		return ans[0]


class Solution:

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

	def stoneGameII(self, piles: List[int]) -> int:
		return self.helper(len(piles), 1, 0, piles, {})


class Solution:

	def stoneGameII(self, piles: List[int]) -> int:
		n = len(piles)
		memo = {}

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


class Solution:

	def stoneGameII(self, piles: List[int]) -> int:
		self.piles = piles
		self.memo = {}
		return self.minimax(0, 1, True)

	def minimax(self, start: int, M: int, is_player_1: bool) -> int:
		if start >= len(self.piles):
			return 0
		if (start, M, is_player_1) in self.memo:
			return self.memo[start, M, is_player_1]
		if is_player_1:
			output = max([sum(self.piles[start:start + x]) + self.minimax(start + x, max(x, M), False) for x in range(1, min(2 * M, len(self.piles)) + 1)])
		else:
			output = min([self.minimax(start + x, max(x, M), True) for x in range(1, min(2 * M, len(self.piles)) + 1)])
		self.memo[start, M, is_player_1] = output
		return output


from functools import lru_cache

class Solution:

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

		def alex(idx, M, score_alex, score_lee):
			if idx == len(piles):
				return (score_alex, score_lee)
			if idx == len(piles) - 1:
				return (score_alex + piles[idx], score_lee)
			(maxa, countl) = (score_alex, score_lee)
			for i in range(1, 2 * M + 1):
				if idx + i <= len(piles):
					(sa, sl) = lee(idx + i, i, score_alex + sum(piles[idx:idx + i]), score_lee)
					if maxa < sa:
						maxa = sa
						countl = sl
				else:
					break
			return (maxa, countl)

		def lee(idx, M, score_alex, score_lee):
			if idx == len(piles):
				return (score_alex, score_lee)
			if idx == len(piles) - 1:
				return (score_alex, score_lee + piles[idx])
			(counta, maxl) = (score_alex, score_lee)
			for i in range(1, 2 * M + 1):
				if idx + i <= len(piles):
					(sa, sl) = alex(idx + i, i, score_alex, score_lee + sum(piles[idx:idx + i]))
					if maxl < sl:
						maxl = sl
						counta = sa
				else:
					break
			return (counta, maxl)

		@lru_cache(None)
		def minimax(i, m, player):
			if i >= len(piles):
				return 0
			if player == 0:
				return max((sum(piles[i:i + j]) + minimax(i + j, max(m, j), player ^ 1) for j in range(1, 2 * m + 1)))
			else:
				return min((minimax(i + j, max(m, j), player ^ 1) for j in range(1, 2 * m + 1)))
		return minimax(0, 1, 0)


from collections import defaultdict

class Solution:

	def stoneGameII(self, piles: List[int]) -> int:
		N = len(piles)
		dp = defaultdict(dict)
		M = 1
		return self.DP(N, dp, piles, M, 0)

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