Intuition¶

The merging rule looks like it creates a complicated evolving row, but it hides a much smaller game. After any sequence of moves the row is always

[ one merged stone ][ untouched original stones ]

and the merged stone's value is exactly the prefix sum of every original stone consumed so far. So the entire position is described by a single number: how far into the original array the players have eaten.

That gives the key fact. If a player's move ends at original index j, the score they add is prefix[j] — the sum of stones[0..j] — no matter how the earlier stones were split between the two players. History does not matter, only j.

Approach: Suffix DP over Prefix Sums¶

Let prefix[j] be the sum of stones[0..j] inclusive, and let state i mean "original stones 0..i are merged into the single leftmost stone". The game starts at state 0 and ends at state n - 1, when one stone remains.

From state i the player to move must take at least two stones — the merged one plus at least one original — so they choose some j > i, score prefix[j], and hand over state j. Writing $$f(i)$$ for the best achievable (current player − opponent) difference from state i:

$$f(i) = \max_{j > i} \left( \text{prefix}[j] - f(j) \right), \qquad f(n-1) = 0$$

The subtraction is what makes one formula serve both players: after the move the opponent becomes "current", so their advantage counts against the mover. The answer is $$f(0)$$.

Collapsing to one pass¶

Evaluated directly this is $$O(n^2)$$. But the set of choices at state i is just the choices at state i + 1 plus the single new option j = i + 1, and the maximum over that older set is by definition $$f(i)$$'s own neighbour:

$$\max_{j > i+1} \left( \text{prefix}[j] - f(j) \right) = f(i+1)$$

so the recurrence collapses to a two-term maximum:

$$f(i) = \max\left( f(i+1),\; \text{prefix}[i+1] - f(i+1) \right)$$

Now a single running variable suffices. Read it as: either decline the shortest move and keep whatever the next state was worth, or take everything through i + 1 and pay back the opponent's best reply.

Why the loop runs from the right and stops at index 1¶

Two details in the code follow from the recurrence.

Start at prefix[n-1], the full total. State n - 2 has exactly one legal move — take everything — so $$f(n-2) = \text{prefix}[n-1]$$. That is the seed.
Stop once prefix[1] has been used. The answer is $$f(0)$$, whose smallest option is j = 1, i.e. taking the first two stones. Indices below that are never legal targets, because a move must consume more than one stone.

Rather than materialising a prefix array, the code walks the total downward: starting from prefix[n-1] and subtracting stones[i+1] leaves exactly prefix[i]. That keeps the whole thing in $$O(1)$$ space. The variable named sum / total / s in the three versions always holds a prefix sum at the moment it is used.

Worked example¶

stones = [-1, 2, -3, 4, -5], so prefix = [-1, 1, -2, 2, -3].

step	index `i`	running sum = `prefix[i]`	`sum - ans`	new `ans` = $$f(i-1)$$
init	—	`prefix[4] = -3`	—	`-3` (this is $$f(3)$$)
1	3	`prefix[3] = 2`	`2 - (-3) = 5`	`max(-3, 5) = 5`
2	2	`prefix[2] = -2`	`-2 - 5 = -7`	`max(5, -7) = 5`
3	1	`prefix[1] = 1`	`1 - 5 = -4`	`max(5, -4) = 5`

The answer is 5, matching the statement's walkthrough where Alice scores 2 and Bob scores -3. Step 1 is the move that matters: Alice takes through index 3 for prefix[3] = 2, leaving Bob a position worth -3 to him.

Edge cases¶

n == 2. No loop iteration runs, and the answer is the seed prefix[1], the sum of both stones. Alice has exactly one legal move. Example 3 gives -10 + -12 = -22.
All stones negative. The answer is not simply the total. For n >= 3 with every stone -10, the result is +10: Alice takes the smallest possible bite and the forced continuations hurt Bob more than her. Verified against a brute-force search of the full game tree.
No 32-bit overflow. With $$n \le 10^5$$ and $$|stones[i]| \le 10^4$$ the total is bounded by $$10^9$$, and every intermediate stays there too, roughly half of i32's range. Checked with adversarial inputs against an i64 run.

Complexity¶

Time complexity: $$O(n)$$ — one pass to total the array and one pass back down.
Space complexity: $$O(1)$$ for the Go and Rust versions. The Python version is $$O(n)$$ because stones[2:] copies the tail; iterating indices instead would make it $$O(1)$$.

Code¶

Go¶

/* dp[i] is optimial difference score of Alice and Bob: from i -> n - 1
Let's say:
dp[i] = max(dp[i+1], sumOf(i, n - 1) - dp[i+1])
*/
func stoneGameVIII(stones []int) int {
    n := len(stones)
    sum := 0
    for _, stone := range stones {
        sum += stone
    }
    ans := sum
    for i := n - 2; i >= 1; i-- {
        sum -= stones[i+1]
        ans = max(ans, sum - ans)
    }
    return ans
}

The builtin max requires Go 1.21 or newer.

Rust¶

impl Solution {
    pub fn stone_game_viii(stones: Vec<i32>) -> i32 {
        let n = stones.len();
        let mut total: i32 = stones.iter().sum();
        let mut ans = total;
        for i in (1..n-1).rev() {
            total -= stones[i+1];
            ans = ans.max(total - ans);
        }
        ans
    }
}

(1..n-1).rev() walks n-2 down to 1, matching the Go loop. When n == 2 the range 1..1 is empty, so the seed is returned untouched.

Python¶

class Solution:
    def stoneGameVIII(self, stones: List[int]) -> int:
        s = sum(stones)
        ans = s
        for stone in reversed(stones[2:]):
            s -= stone
            ans = max(ans, s - ans)
        return ans

Subtracting stones[n-1] down to stones[2] produces prefix[n-2] down to prefix[1] — the same sequence the indexed loops visit.

Test cases¶

`stones`	answer	note
`[-1,2,-3,4,-5]`	`5`	Example 1, traced above
`[7,-6,5,10,5,-2,-6]`	`13`	Example 2 — Alice takes everything
`[-10,-12]`	`-22`	Example 3 — only one legal move
`[-10,-10,-10]`	`10`	all-negative, answer is positive
`[10000] * 100000`	`10^9`	upper bound on the total

All three implementations were run against an $$O(n^2)$$ reference derived straight from the game rules: 20000 random arrays with n in [2, 9] agree with no mismatches, and Go, Rust and Python return identical results on a shared corpus of 20003 cases including the three examples.