Alice and Bob take turns playing a game, with Alice starting first.
There are n stones arranged in a row. On each player's turn, while the number of stones is more than one, they will do the following:
x > 1, and remove the leftmost x stones from the row.The game stops when only one stone is left in the row.
The score difference between Alice and Bob is (Alice's score - Bob's score). Alice's goal is to maximize the score difference, and Bob's goal is the minimize the score difference.
Given an integer array stones of length n where stones[i] represents the value of the ith stone from the left, return the score difference between Alice and Bob if they both play optimally.
Example 1:
Input: stones = [-1,2,-3,4,-5] Output: 5 Explanation: - Alice removes the first 4 stones, adds (-1) + 2 + (-3) + 4 = 2 to her score, and places a stone of value 2 on the left. stones = [2,-5]. - Bob removes the first 2 stones, adds 2 + (-5) = -3 to his score, and places a stone of value -3 on the left. stones = [-3]. The difference between their scores is 2 - (-3) = 5.
Example 2:
Input: stones = [7,-6,5,10,5,-2,-6] Output: 13 Explanation: - Alice removes all stones, adds 7 + (-6) + 5 + 10 + 5 + (-2) + (-6) = 13 to her score, and places a stone of value 13 on the left. stones = [13]. The difference between their scores is 13 - 0 = 13.
Example 3:
Input: stones = [-10,-12] Output: -22 Explanation: - Alice can only make one move, which is to remove both stones. She adds (-10) + (-12) = -22 to her score and places a stone of value -22 on the left. stones = [-22]. The difference between their scores is (-22) - 0 = -22.
Constraints:
n == stones.length2 <= n <= 105-104 <= stones[i] <= 104Problem Overview: You are given an integer array where two players take turns removing stones from the left and adding the removed stones' sum to their score. Each move must remove at least two stones. Both players play optimally, and the goal is to compute the maximum score difference the first player can achieve.
This problem mixes array manipulation with optimal play strategy from game theory. The key observation is that once stones are removed, the remaining prefix sums determine the score impact of each move. Efficient solutions rely on prefix sum preprocessing and dynamic programming.
Approach 1: Dynamic Programming with Suffix Sums (O(n) time, O(n) space)
Start by computing a prefix sum array where prefix[i] represents the total of the first i+1 stones. When a player removes the first i+1 stones, they gain prefix[i] points and the game continues with the remaining suffix. Define a DP array dp[i] representing the best score difference the current player can achieve starting from position i. Iterate from right to left. For each index, choose between taking the current prefix or skipping to a later position. The recurrence becomes dp[i] = max(dp[i+1], prefix[i] - dp[i+1]). This works because the opponent will also play optimally, so their best outcome reduces the current player’s advantage. The approach runs in O(n) time with O(n) additional memory for the DP array.
Approach 2: Optimized Dynamic Programming (O(n) time, O(1) space)
The DP recurrence only depends on the next state, which means the entire DP array is unnecessary. Maintain a single variable representing the best score difference seen so far while iterating backward through the prefix sums. Start with the total prefix sum at the end and update the best value using the same transition best = max(best, prefix[i] - best). This preserves the same game-state logic but compresses the DP state into one variable. The algorithm still scans the array once after computing prefix sums, so the time complexity stays O(n) while space drops to O(1). This is the version typically used in competitive programming and production solutions.
Recommended for interviews: The optimized dynamic programming approach is what interviewers usually expect. Building the prefix sum and deriving the recurrence shows understanding of how score differences propagate in adversarial games. Mentioning the full DP array first demonstrates the reasoning process, then reducing it to O(1) space shows strong optimization skills.
This approach leverages dynamic programming and suffix sum calculations. We start by calculating the suffix sum for each stone position, which gives the sum of all stones from that position to the end. Our goal is to maximize the score difference Alice can achieve taking turns optimally with Bob. We will use a dp array to track the maximum result from each position onward.
The solution defines a stoneGameVIII function that calculates the suffix sum of the given stone array from the end to the beginning. Next, it initializes a dp array to keep track of the maximum differences from each position onward. The final result, dp[0], is the answer returned.
Time Complexity: O(n), where n is the length of the stones array, because we iterate over the array twice.
Space Complexity: O(n), for storing the suffix sums and the dp array.
This approach tries to optimize the space complexity of the earlier approach by eliminating the need to store the entire dp array. Instead, we can maintain just the current and previous values needed to make the decision. This reduces the space needed significantly while maintaining accuracy.
By keeping track of only the maximum difference, rather than an entire array of results, this Python function improves on space efficiency. The max_diff variable holds the optimal value from the end toward the start.
Time Complexity: O(n).
Space Complexity: O(1), since we no longer need the full dp array.
According to the problem description, each time we take the leftmost x stones, add their sum to our score, and then put a stone with this sum value on the leftmost side, it is equivalent to merging these x stones into a stone with this sum value, and the prefix sum remains unchanged.
We can use a prefix sum array s of length n to represent the prefix sum of the array stones, where s[i] represents the sum of the elements stones[0..i].
Next, we design a function dfs(i), which means that we currently take stones from stones[i:], and return the maximum score difference that the current player can get.
The execution process of the function dfs(i) is as follows:
i geq n - 1, it means that we can only take all the stones at present, so we return s[n - 1].stones[i + 1:], and the score difference obtained is dfs(i + 1); we can also choose to take the stones stones[:i], and the score difference obtained is s[i] - dfs(i + 1). We take the maximum of the two situations, which is the maximum score difference that the current player can get.Finally, we can get the score difference between Alice and Bob as dfs(1), that is, Alice must start the game by taking stones from stones[1:].
To avoid repeated calculations, we can use memoization search.
The time complexity is O(n), and the space complexity is O(n). Here, n is the length of the array stones.
Python
Java
C++
Go
TypeScript
We can also use dynamic programming to solve this problem.
Similar to Solution 1, we first use a prefix sum array s of length n to represent the prefix sum of the array stones, where s[i] represents the sum of the elements stones[0..i].
We define f[i] to represent the maximum score difference that the current player can get when taking stones from stones[i:].
If the player chooses to take the stones stones[:i], then the score obtained is s[i]. At this time, the other player will take stones from stones[i+1:], and the maximum score difference that the other player can get is f[i+1]. Therefore, the maximum score difference that the current player can get is s[i] - f[i+1].
If the player chooses to take stones from stones[i+1:], then the maximum score difference obtained is f[i+1].
Therefore, we can get the state transition equation:
$
f[i] = max{s[i] - f[i+1], f[i+1]}
Finally, we can get the score difference between Alice and Bob as f[1], that is, Alice must start the game by taking stones from stones[1:].
We notice that f[i] is only related to f[i+1], so we only need to use a variable f to represent f[i].
The time complexity is O(n), and the space complexity is O(1). Here, n is the length of the array stones$.
Python
Java
C++
TypeScript
| Approach | Complexity |
|---|---|
| Approach 1: Dynamic Programming with Suffix Sums | Time Complexity: O(n), where n is the length of the stones array, because we iterate over the array twice. |
| Approach 2: Optimized Dynamic Programming | Time Complexity: O(n). |
| Prefix Sum + Memoization Search | — |
| Prefix Sum + Dynamic Programming | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Dynamic Programming with Suffix Sums | O(n) | O(n) | Useful when first deriving the DP transition and explaining the game state clearly |
| Optimized Dynamic Programming | O(n) | O(1) | Best for production or interviews where memory optimization is expected |
花花酱 LeetCode 1872. Stone Game VIII - 刷题找工作 EP394 • Hua Hua • 4,032 views views
Watch 8 more video solutions →Practice Stone Game VIII with our built-in code editor and test cases.
Practice on FleetCode