Alice and Bob continue their&nbsp;games with piles of stones.&nbsp; There are a number of&nbsp;piles&nbsp;arranged in a row, and each pile has a positive integer number of stones&nbsp;piles[i].&nbsp; The objective of the game is to end with the most&nbsp;stones.&nbsp;

Alice&nbsp;and Bob take turns, with Alice starting first.&nbsp; Initially, M = 1.

On each player's turn, that player&nbsp;can take all the stones in the first X remaining piles, where 1 &lt;= X &lt;= 2M.&nbsp; Then, we set&nbsp;M = max(M, X).

The game continues until all the stones have been taken.

Assuming Alice and Bob play optimally, return the maximum number of stones Alice&nbsp;can get.

&nbsp;
Example 1:

Input: piles = [2,7,9,4,4]
Output: 10
Explanation:  If Alice takes one pile at the beginning, Bob takes two piles, then Alice takes 2 piles again. Alice can get 2 + 4 + 4 = 10 piles in total. If Alice takes two piles at the beginning, then Bob can take all three piles left. In this case, Alice get 2 + 7 = 9 piles in total. So we return 10 since it's larger. 


Example 2:

Input: piles = [1,2,3,4,5,100]
Output: 104


&nbsp;
Constraints:


	1 &lt;= piles.length &lt;= 100
	1 &lt;= piles[i]&nbsp;&lt;= 104


class Solution:
    def stoneGameII(self, piles: List[int]) -> int:
        n = len(piles)
        dp = {} 
        def recursion(index,M):
            # if we reached to the end we cannot score any value
            if index == n:
                return 0
            # we search if we have solved the same case earlier
            if (index,M) in dp:
                return dp[(index,M)] 
            # total remaining score is the sum of array from index to the end
            total = sum(piles[index:])           
            # if we can take the complete array it is the best choice
            if index + 2*M >= n :return total
            # my_score is the score we are getting as the player who is playing
            my_score = 0
            for x in range(index,index+2*M):
                # opponent score will be calculated by next recursion
                opponent_score = recursion(x+1,max(M,x-index+1))
                # my_score is the remaining value of total - opponent_score
                my_score = max(my_score,total - opponent_score)          
            # this is memoization part
            dp[(index,M)] = my_score
            # return the score
            return my_score
        
        return recursion(0,1)
class Solution {
    public int stoneGameII(int[] piles) {
        Map<String, Integer> memo = new HashMap<>();
        int diff = stoneGame(piles,1,0,0,memo);
        int totalSum = 0;
        for(int ele: piles)
            totalSum+=ele;
        return (diff+totalSum)/2;
    }

    public int stoneGame(int[] piles, int M, int index, int turn,Map<String, Integer> memo )
    {
        if(index >= piles.length)
            return 0;
        if(memo.containsKey(index+"-"+M+"-"+turn))
            return memo.get(index+"-"+M+"-"+turn);
        int score=0,maxScore=Integer.MIN_VALUE;
        // Alice's turn
        if(turn == 0)
        {
            for(int X=1;X<=2*M && index+X-1<piles.length;X++)
            {
                score += piles[index+X-1];
                maxScore= Math.max(maxScore,stoneGame(piles,Math.max(X,M),index+X,1,memo)+score);
            }
            memo.put(index+"-"+M+"-"+turn,maxScore);
            return maxScore;
        }
        // Bob's turn
        int minScore=Integer.MAX_VALUE;
        for(int X=1;X<=2*M && index+X-1<piles.length;X++)
        {
            score += piles[index+X-1];
            minScore = Math.min(minScore, stoneGame(piles,Math.max(X,M),index+X,0,memo) - score ) ;
        }
        memo.put(index+"-"+M+"-"+turn,minScore);
        return minScore;
    }

}
class Solution {
public:
    int dp[103][103][2];
    int rec(int i,int m,int p,vector<int>& piles){
        if(i==piles.size()) return 0;
        if(dp[i][m][p]!=-1) return dp[i][m][p];
        int cnt = 0,ans=INT_MIN,n=piles.size();
        for(int j=i;j<min(n,i+2*m);j++){
            cnt += piles[j];
            ans =max(ans, cnt - rec(j+1,max(j-i+1,m),1-p,piles));
        }
        return dp[i][m][p] = ans;
    }
    int stoneGameII(vector<int>& piles) {
        int sum = 0;
        memset(dp,-1,sizeof(dp));
        for(auto i:piles) sum += i;
        return (sum + rec(0,1,0,piles))/2;
    }
};
var stoneGameII = function(piles) {
  const length = piles.length;
  const dp = [...Array(length + 1).fill(null)].map((_) =>
    Array(length + 1).fill(0)
  );
  const sufsum = new Array(length + 1).fill(0);
  for (let i = length - 1; i >= 0; i--) {
    sufsum[i] = sufsum[i + 1] + piles[i];
  }
  for (let i = 0; i <= length; i++) {
    dp[i][length] = sufsum[i];
  }
  for (let i = length - 1; i >= 0; i--) {
    for (let j = length - 1; j >= 1; j--) {
      for (let X = 1; X <= 2 * j && i + X <= length; X++) {
        dp[i][j] = Math.max(dp[i][j], sufsum[i] - dp[i + X][Math.max(j, X)]);
      }
    }
  }
  return dp[0][1];
};
Stone Game II