<p>Alice and Bob continue their games with piles of stones. There are several stones <strong>arranged in a row</strong>, and each stone has an associated value which is an integer given in the array <code>stoneValue</code>.</p>

<p>Alice and Bob take turns, with Alice starting first. On each player&#39;s turn, that player can take <code>1</code>, <code>2</code>, or <code>3</code> stones from the <strong>first</strong> remaining stones in the row.</p>

<p>The score of each player is the sum of the values of the stones taken. The score of each player is <code>0</code> initially.</p>

<p>The objective of the game is to end with the highest score, and the winner is the player with the highest score and there could be a tie. The game continues until all the stones have been taken.</p>

<p>Assume Alice and Bob <strong>play optimally</strong>.</p>

<p>Return <code>&quot;Alice&quot;</code><em> if Alice will win, </em><code>&quot;Bob&quot;</code><em> if Bob will win, or </em><code>&quot;Tie&quot;</code><em> if they will end the game with the same score</em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> stoneValue = [1,2,3,7]
<strong>Output:</strong> &quot;Bob&quot;
<strong>Explanation:</strong> Alice will always lose. Her best move will be to take three piles and the score become 6. Now the score of Bob is 7 and Bob wins.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> stoneValue = [1,2,3,-9]
<strong>Output:</strong> &quot;Alice&quot;
<strong>Explanation:</strong> Alice must choose all the three piles at the first move to win and leave Bob with negative score.
If Alice chooses one pile her score will be 1 and the next move Bob&#39;s score becomes 5. In the next move, Alice will take the pile with value = -9 and lose.
If Alice chooses two piles her score will be 3 and the next move Bob&#39;s score becomes 3. In the next move, Alice will take the pile with value = -9 and also lose.
Remember that both play optimally so here Alice will choose the scenario that makes her win.
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> stoneValue = [1,2,3,6]
<strong>Output:</strong> &quot;Tie&quot;
<strong>Explanation:</strong> Alice cannot win this game. She can end the game in a draw if she decided to choose all the first three piles, otherwise she will lose.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= stoneValue.length &lt;= 5 * 10<sup>4</sup></code></li>
	<li><code>-1000 &lt;= stoneValue[i] &lt;= 1000</code></li>
</ul>

class Solution {
public:
    int dp[50000];
    int solve(vector<int> &nums,int i){
        if(i>=nums.size()){
            return INT_MIN/2;
        }
        // int ans;
        // min({solve(arr,i+2), solve(arr,i+3), solve(arr,i+4)}) +arr[i], 

        //     min({solve(arr,i+3), solve(arr,i+4), solve(arr,i+5)}) + arr[i]+arr[i+1],
        //     min({solve(arr,i+4), solve(arr,i+5), solve(arr,i+6)})+ arr[i]+arr[i+1]+arr[i+2]

        int sum=0;
        int finalSum=INT_MIN/2;
        // if(i==0){

        if(dp[i]!=INT_MIN/2){
            return dp[i];
        }
        for(int j=0;(i+j)<nums.size() && j<3;j++){
            sum+=nums[i+j];
            int ans=INT_MAX/2;
            for(int k=1;k<=3;k++){
                if((i+j+k+1)<nums.size()){
                    ans=min(ans, solve(nums, i+j+k+1));
                }
                else{
                    ans=min(ans,0);
                }
                
            }
            
            if(ans==INT_MAX/2){
                ans=0;
            }
            // if(i==0){
            //     cout<<(i+j)<<" - ";
            //     // cout<<(ans+sum)<<"\n";
            // }
            ans+=sum;
            finalSum=max(finalSum, ans);
        // }
        }
        // cout<<i<<" "<<finalSum<<"\n";
        return dp[i]=finalSum;
            
    }
    string stoneGameIII(vector<int>& stoneValue) {
        for(int i=0;i<stoneValue.size();i++){
            dp[i]=INT_MIN/2;
        }
        int sum=0;
        for(int i=0;i<stoneValue.size();i++){
            sum+=stoneValue[i];
        }
        int alice=solve(stoneValue,0);
        int bob=sum-alice;
        cout<<alice<<" "<<bob<<"\n";
        if(alice>bob){
            return "Alice";

        }
        else if(alice==bob){
            return "Tie";
        }
        else{
            return "Bob";
        }
    }
};
131918