Stone Game VIII: Prefix Sums Meet Game Theory

There are n stones in a row, each with an integer value. Alice and Bob take turns picking up stones, with Alice going first. On each turn, the player picks up the leftmost x stones (where x >= 2), removes them, and places a single new stone at the left position whose value equals the sum of those x stones. The player's score for that turn is the sum of the stones they picked up. Both players play optimally to maximize their own score minus their opponent's score. Return the maximum score difference Alice can achieve.

This is LeetCode 1872: Stone Game VIII, a hard problem that looks like it requires complex game simulation. But underneath the game mechanics lies a clean DP on prefix sums that runs in O(n) time.

The problem

Given stones = [-1, 2, -3, 4, -5]:

• Alice must pick at least the first 2 stones. She can pick 2, 3, 4, or all 5.
• Whatever she picks, she scores their sum and places a replacement stone with that sum value at the left.
• Bob then does the same from the new left end.
• Both play optimally. Alice wants to maximize Alice_score - Bob_score, Bob wants to minimize it.

For this example, Alice can guarantee a score difference of 5. The trick is realizing you never need to simulate the stone replacement at all. Every possible move maps directly to a prefix sum.

The brute force approach

A naive approach would simulate every possible game state. On each turn, the current player chooses how many stones to pick up (from 2 to however many remain). This creates a game tree where each node branches into multiple children. The number of possible game states grows exponentially with the number of stones, making a direct recursive simulation far too slow for the constraint of n up to 10^5.

You could add memoization, but the game state (which stones remain, whose turn it is) is hard to compress into a clean key. The game tree has too many branches and the state space is too large. We need a fundamentally different angle.

The key insight: prefix sums simplify everything

Here is the critical observation. When a player picks up the first x stones, their score is stones[0] + stones[1] + ... + stones[x-1]. But after the replacement, the new leftmost stone has value stones[0] + stones[1] + ... + stones[x-1], which is exactly the same sum. So the replacement stone already "contains" all the information about the removed stones.

This means every future pick that includes the replacement stone will add that prefix sum again. The entire game can be expressed in terms of the prefix sum array prefix[i] = stones[0] + stones[1] + ... + stones[i]. When a player decides to pick up through index i, their score for that turn is simply prefix[i].

The DP recurrence

Define dp[i] as the maximum score difference the current player can achieve when the earliest available choice is index i. The current player has two options:

1. Pick index i: score prefix[i], then the opponent faces dp[i+1]. The net difference is prefix[i] - dp[i+1].
2. Skip index i: pass this choice to a future turn. The current player's best outcome is dp[i+1].

So the recurrence is:

dp[i] = max(prefix[i] - dp[i+1], dp[i+1])

We scan from right to left. The base case is dp[n-1] = prefix[n-1], since the only option at the last index is to pick everything.

Since each player must pick at least 2 stones, the first valid prefix index is 1 (representing picking stones[0] and stones[1]). The answer is dp[1].

Visual walkthrough

Using stones = [-1, 2, -3, 4, -5], the prefix sum array is [-1, 1, -2, 2, -3]. We scan from dp[4] down to dp[1].

The code

def stoneGameVIII(stones):
    n = len(stones)
    for i in range(1, n):
        stones[i] += stones[i - 1]

    dp = stones[n - 1]
    for i in range(n - 2, 0, -1):
        dp = max(stones[i] - dp, dp)

    return dp

There are a few things worth noting in this implementation. First, we build the prefix sums in place by overwriting the stones array. After the loop, stones[i] holds the prefix sum through index i. This avoids allocating a separate array.

Second, we do not store the entire dp array. Since dp[i] only depends on dp[i+1], a single variable is enough. We initialize it to stones[n-1] (the base case dp[n-1]) and scan leftward, updating in place.

Third, the loop runs from n-2 down to 1, not down to 0. Index 0 represents picking just one stone, which violates the x >= 2 rule. The answer is the value of dp after the loop finishes, which corresponds to dp[1].

Complexity analysis

Time: O(n). Computing prefix sums takes O(n). The right-to-left DP scan also takes O(n). Total: O(n).

Space: O(1). We modify the input array in place for prefix sums and use a single variable for the DP. If you cannot modify the input, you can compute prefix sums in a separate array for O(n) space.

Edge cases to watch for

• All positive values: the prefix sums are strictly increasing. Alice should pick all stones on her first turn, scoring prefix[n-1]. Bob never gets a turn.
• All negative values: Alice still must pick at least 2 stones. The DP correctly handles negative prefix sums by comparing picking now versus deferring.
• Two stones (n = 2): Alice must pick both. The answer is stones[0] + stones[1]. The loop body never executes, and dp = prefix[1] from initialization, which is correct since prefix[n-1] = prefix[1] when n = 2.
• Large n (up to 10^5): the O(n) algorithm handles this without issue. No recursion depth concerns since the solution is iterative.

The building blocks

This problem combines two reusable patterns:

Prefix sum reduction. Many problems that seem to require tracking individual elements can be rephrased in terms of prefix sums. Here, the game mechanics of stone replacement are just a distraction. Once you see that every move scores a prefix sum, the problem collapses from a complex game simulation to a simple array scan. This same reduction appears in Maximum Subarray and other problems where contiguous sums matter.

Game theory DP with alternating players. The recurrence dp[i] = max(score - dp[i+1], dp[i+1]) is a classic pattern for two-player zero-sum games. The key idea is that your opponent also plays optimally, so your net gain from a move is your score minus whatever advantage the opponent gets from the remaining game. This pattern connects to the entire Stone Game family and problems like Predict the Winner.

From understanding to recall

You now see how the stone replacement mechanic reduces to prefix sums and how the game theory DP collapses to a single right-to-left scan. But reproducing this under time pressure is a different skill.

In an interview, you need to quickly spot the prefix sum connection, derive the dp[i] = max(prefix[i] - dp[i+1], dp[i+1]) recurrence, recognize that the loop starts at index 1 (not 0), and implement the O(1) space optimization. Each of these steps is a potential stumbling point, and fluency comes from repetition, not just understanding.

Spaced repetition closes the gap. You revisit this problem at increasing intervals, each time deriving the prefix sum reduction and writing the DP from scratch. After a few reps, the pattern of "game score equals prefix sum, so reduce and scan" becomes automatic. You see a stone-merging game and immediately think prefix sums.

The prefix sum reduction and game theory DP patterns are two of roughly 60 reusable building blocks that cover hundreds of LeetCode problems. Learning them individually and drilling with spaced repetition is far more effective than grinding problems randomly.

Related posts

• Maximum Subarray - Another problem where prefix sums unlock a linear-time solution
• Coin Change - Classic bottom-up DP with optimal substructure, a foundational pattern for game theory DP
• Best Time to Buy and Sell Stock III - State-based DP with multiple passes, another hard problem simplified by the right perspective