Stone Game VIII

Hard
1064.

Stone Game VIII

Stone Game VIII is a hard coding problem on arrays, dynamic programming and math, asked in Amazon, Google and Meta interviews.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} stones
 * @return {number}
 */
var stoneGameVIII = function(stones) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Stone Game VIII — Solution in Python, Java & C++

Stone Game VIII solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.

Stone Game VIII is a hard coding problem on arrays, dynamic programming and math, asked in Amazon, Google and Meta interviews.

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

Hints for Stone Game VIII

  1. Hint 1

    After any move the row is always "a merged stone followed by an untouched suffix", and the merged stone's value is a prefix sum of the original array.

  2. Hint 2

    So the whole game is: the mover picks a prefix-sum index i >= 1, scores pre[i], and the opponent then plays from index i+1 onwards.

  3. Hint 3

    Sweep i from the end: the best for the mover is max(best_from_i+1, pre[i] - best_from_i+1).

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

  1. Build prefix sums pre.
  2. Initialise best = pre[n-1] — the last possible move takes everything.
  3. Sweep i from n-2 down to 1, setting best = max(best, pre[i] - best).
  4. 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

Java

public static int stoneGameVIII(int[] stones) {
    int n = stones.length;
    int[] pre = new int[n];
    pre[0] = stones[0];
    for (int i = 1; i < n; i++) pre[i] = pre[i - 1] + stones[i];
    int best = pre[n - 1];
    for (int i = n - 2; i >= 1; i--) best = Math.max(best, pre[i] - best);
    return best;
}

C++

int stoneGameVIII(vector<int>& stones) {
    int n = (int) stones.size();
    vector<int> pre(n, 0);
    pre[0] = stones[0];
    for (int i = 1; i < n; i++) pre[i] = pre[i - 1] + stones[i];
    int best = pre[n - 1];
    for (int i = n - 2; i >= 1; i--) 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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Dynamic Programming