<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 {
    // Function to simulate Bob's turn
    pair<int, int> playBob(int s, vector<int>& piles, vector<pair<int, int>>& dpA, vector<pair<int, int>>& dpB)
    {
        // Base case: If all piles have been played, return score (0, 0)
        if(s == piles.size()) {
            return {0, 0};
        }
        // If the result for Bob's turn at this state has already been computed, return it
        if(dpB[s].first != -1) {
            return dpB[s];
        }
        int sum = 0;
        int a = -1e9; // Alice's score initialized to a very low value
        int b = -1e9; // Bob's score initialized to a very low value

        // Consider the next three piles or the remaining piles if less than three
        for(int i = s; i - s < 3 && i < piles.size(); i++) {
            sum += piles[i];
            // Recursively simulate Alice's turn after Bob chooses the current pile(s)
            auto res = playAlice(i + 1, piles, dpA, dpB);

            // Update Bob's score if it is higher than the current maximum
            if(b < sum + res.second) {
                a = res.first; // Update Alice's score
                b = sum + res.second; // Update Bob's score
            }
        }
        // Memoize the result for Bob's turn at this state and return it
        return dpB[s] = {a, b};
    }

    // Function to simulate Alice's turn
    pair<int, int> playAlice(int s, vector<int>& piles, vector<pair<int, int>>& dpA, vector<pair<int, int>>& dpB)
    {
        // Base case: If all piles have been played, return score (0, 0)
        if(s == piles.size()) {
            return {0, 0};
        }
        // If the result for Alice's turn at this state has already been computed, return it
        if(dpA[s].first != -1) {
            return dpA[s];
        }
        int sum = 0;
        int a = -1e9; // Alice's score initialized to a very low value
        int b = -1e9; // Bob's score initialized to a very low value

        // Consider the next three piles or the remaining piles if less than three
        for(int i = s; i - s < 3 && i < piles.size(); i++) {
            sum += piles[i];
            // Recursively simulate Bob's turn after Alice chooses the current pile(s)
            auto res = playBob(i + 1, piles, dpA, dpB);

            // Update Alice's score if it is higher than the current maximum
            if(a < sum + res.first) {
                b = res.second; // Update Bob's score
                a = sum + res.first; // Update Alice's score
            }
        }
        // Memoize the result for Alice's turn at this state and return it
        return dpA[s] = {a, b};
    }

public:
    string stoneGameIII(vector<int>& piles)
    {
        // Create memoization arrays for storing previously computed results
        vector<pair<int, int>> dpA(piles.size(), {-1, -1}); // dpA[i] stores the maximum scores for Alice starting at pile i
        vector<pair<int, int>> dpB(piles.size(), {-1, -1});

        // Simulate Alice's turn from the beginning of the game
        auto res = playAlice(0, piles, dpA, dpB);

        // Compare Alice's and Bob's scores to determine the winner
        if(res.first > res.second) {
            return "Alice"; // Alice has a higher score
        }
        if(res.first < res.second) {
            return "Bob"; // Bob has a higher score
        }
        return "Tie"; // Scores are equal, it's a tie
    }
};
158483