Watch 9 video solutions for Stone Game VIII, a hard level problem involving Array, Math, Dynamic Programming. This walkthrough by Hua Hua has 4,032 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |