Stone Game VIII — Hard Problem & Solution

Alice and Bob take turns, Alice first. While more than one stone remains, the player to move chooses an integer x > 1, removes the first x stones, scores…

Difficulty: Hard
Topics: Arrays, Math, Dynamic Programming, Prefix Sum, Game Theory
Asked at: Amazon, Google, Meta
Time limit: 2 s
Memory limit: 256 MB
Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

Alice and Bob take turns, Alice first. While more than one stone remains, the player to move chooses an integer x > 1, removes the first x stones, scores their sum, and puts a new stone of that value at the front of the row.

Alice maximises the difference between her score and Bob's; Bob minimises it. Return that difference with both playing optimally.

Example 1

Input: stones = [-1,2,-3,4,-5]
Output: 5
Explanation: Alice takes the first four, scoring 2; the row becomes `[2,-5]` and Bob must take both, scoring −3.

Example 2

Input: stones = [7,-6,5,10,5,-2,-6]
Output: 13

Example 3

Input: stones = [-10,-12]
Output: -22
Explanation: Alice has no choice but to take both stones.

Constraints

n == stones.length
2 <= n <= 10^5
-10^4 <= stones[i] <= 10^4

How to solve Stone Game VIII

Every position is described by a single index: the merged stone is always pre[i] for some prefix i, and the untouched stones are i+1..n-1. A move from state i scores pre[j] for some j > i and hands the opponent state j. Sweeping from the right, best[i] = max(best[i+1], pre[i] - best[i+1]).

Approach

Build prefix sums pre.
Initialise best = pre[n-1] — the last possible move takes everything.
Sweep i from n-2 down to 1, setting best = max(best, pre[i] - best).
Return best, the value of Alice's first move.

Why it works

The collapse to one index is the entire trick. It looks like a game over arbitrary configurations, but merging means the left part is only ever a single number — its prefix sum — so the state is just "how far in". The recurrence then reads as "either skip this prefix and keep the opponent's best, or take it and subtract what the opponent can force", and sweeping right-to-left makes it O(n). The sweep starts at i = 1 because the first move must take at least two stones.

Complexity

Time — O(n)
Space — O(n), or O(1) folding the prefix sum into the sweep

Pitfalls

x > 1, so the first legal prefix is index 1, not 0.
The base case is pre[n-1] — taking every remaining stone is always available.
The sweep must go right to left; left to right has no correct reading.

Reference solution

Python

from typing import List

def stoneGameVIII(stones: List[int]) -> int:
    n = len(stones)
    pre = [0] * n
    pre[0] = stones[0]
    for i in range(1, n):
        pre[i] = pre[i - 1] + stones[i]
    best = pre[n - 1]
    for i in range(n - 2, 0, -1):
        best = max(best, pre[i] - best)
    return best

JavaScript

var stoneGameVIII = function(stones) {
    var n = stones.length;
    var pre = [];
    for (var t = 0; t < n; t++) pre.push(0);
    pre[0] = stones[0];
    for (var i = 1; i < n; i++) pre[i] = pre[i - 1] + stones[i];
    var best = pre[n - 1];
    for (i = n - 2; i >= 1; i--) {
        var take = pre[i] - best;
        if (take > best) best = take;
    }
    return best;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 667 arrays problems · the whole catalogue