This problem is solved by applying state transition dynamic programming on prefix sums of the stone array. Track the maximum difference achievable for each number of stones removed. Using prefix sums allows updating the DP state efficiently while considering all valid moves, focusing only on how many stones are removed at each step to maximize the score difference.
Problem Statement
Alice and Bob play a turn-based game with a row of stones. On each turn, a player removes at least two stones from the left, sums their values, and places a new stone equal to that sum on the left. Alice moves first, and the game ends when only one stone remains.
Given an array of integers stones representing the stone values, compute the maximum possible difference between Alice's and Bob's scores assuming both play optimally. The constraints are 2 <= stones.length <= 10^5 and -10^4 <= stones[i] <= 10^4.
Examples
Example 1
Input: stones = [-1,2,-3,4,-5]
Output: 5
- 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
- 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
- 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.length
- 2 <= n <= 105
- -104 <= stones[i] <= 104
Solution Approach
Use prefix sums to preprocess moves
Compute prefix sums of stones so any sum of the first k stones can be retrieved in O(1). This allows calculating the resulting new stone value efficiently for each possible removal move.
State transition dynamic programming
Define dp[i] as the maximum score difference starting with the first i stones removed. Use the recurrence dp[i] = max(dp[i-1], prefixSum[i] - dp[i-1]) to consider keeping the previous optimal or taking the new move. Iterate from i = 2 to n.
Optimize using linear scan
Scan the stones array once while maintaining the dp values in a single pass. No nested loops are needed because the recurrence only depends on the previous dp state, keeping time complexity linear.
Complexity Analysis
| Metric | Value |
|---|---|
| Time | Depends on the final approach |
| Space | Depends on the final approach |
Time complexity is O(n) due to single pass DP using prefix sums. Space complexity is O(n) if storing full DP array or O(1) if optimized to keep only previous state.
What Interviewers Usually Probe
- Expecting prefix sum usage for move sums
- Checking understanding of state transition DP
- Looking for handling large n efficiently without nested loops
Common Pitfalls or Variants
Common pitfalls
- Ignoring that at least two stones must be removed per move
- Incorrectly tracking score difference instead of individual scores
- Recomputing prefix sums in inner loops causing TLE
Follow-up variants
- Changing score function to product instead of sum
- Allowing removal of exactly k stones instead of at least two
- Scoring based on alternating stone positions rather than prefix sums
How GhostInterview Helps
- Highlights DP state transitions and prefix sum optimization for Stone Game VIII
- Shows correct way to update dp[i] based on previous state and moves
- Identifies failure modes like miscounting stones removed or recalculating sums
Topic Pages
Related GhostInterview Pages
- LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
- Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
- How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.
FAQ
What is the main pattern in Stone Game VIII?
State transition dynamic programming using prefix sums is the key pattern to compute optimal score difference.
Can Stone Game VIII be solved without prefix sums?
Technically yes, but recomputing sums repeatedly would be inefficient and likely cause TLE for large n.
Why must at least two stones be removed each turn?
This rule ensures the new stone value is meaningful and prevents trivial moves that break the DP recurrence.
What is the optimal way to track DP states?
Maintain dp[i] representing the maximum difference after removing i stones, updating with dp[i] = max(dp[i-1], prefixSum[i] - dp[i-1]).
How does GhostInterview assist for this problem?
It guides solving Stone Game VIII by enforcing correct DP state updates, prefix sum usage, and avoiding common calculation pitfalls.
Need direct help with Stone Game VIII instead of spending more time grinding it?
Download GhostInterview when you want a LeetCode solver, not another long practice loop. Capture Stone Game VIII from a screenshot, get the answer path and complexity, and use supported stealth workflows that stay outside captured layers.
Capture the prompt fast instead of rewriting the problem by hand.
Get the solution path, trade-offs, and complexity summary in one pass.
Stay outside captured layers on supported screen-share workflows.
Stay in the same pattern family
Stone Game II is a dynamic programming problem where Alice and Bob alternate taking stones from piles to maximize their total.
Open problem page#1728 Cat and Mouse IICat and Mouse II requires determining if the mouse can reach food before being caught using graph and topological ordering logic.
Open problem page#1690 Stone Game VIIMaximize score difference in a two-player turn-based stone removal game using state transition dynamic programming.
Open problem page