Stone Game VIII

hard dp prefix sum game theory

Problem

On each turn a player (while > 1 stone remains) chooses x ≥ 2 of the leftmost stones, removes them, scores the sum of those x stones, and places a single new stone with that sum at the left. Alice plays first; both maximize their own score minus the opponent's. Return Alice's score minus Bob's, both playing optimally.

Inputstones = [-1,2,-3,4,-5]

Output5

A move taking the first i+1 stones scores prefix[i]. dp[i] = max(dp[i+1], prefix[i] - dp[i+1]).

stones

def stone_game_viii(stones):
    n = len(stones)
    prefix = [0] * n
    prefix[0] = stones[0]
    for i in range(1, n):
        prefix[i] = prefix[i - 1] + stones[i]
    # Any move ending at index i scores prefix[i].
    best = prefix[n - 1]               # last possible move (must take all)
    for i in range(n - 2, 0, -1):
        best = max(best, prefix[i] - best)
    return best

function stoneGameVIII(stones) {
  const n = stones.length;
  const prefix = new Array(n).fill(0);
  prefix[0] = stones[0];
  for (let i = 1; i < n; i++) prefix[i] = prefix[i - 1] + stones[i];
  let best = prefix[n - 1];
  for (let i = n - 2; i >= 1; i--) {
    best = Math.max(best, prefix[i] - best);
  }
  return best;
}

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

int stoneGameVIII(vector<int>& stones) {
    int n = stones.size();
    vector<int> prefix(n, 0);
    prefix[0] = stones[0];
    for (int i = 1; i < n; i++) prefix[i] = prefix[i - 1] + stones[i];
    int best = prefix[n - 1];
    for (int i = n - 2; i >= 1; i--) {
        best = max(best, prefix[i] - best);
    }
    return best;
}

Explanation

A move always grabs a prefix of the current row and replaces it with one stone equal to its sum. So after any sequence of moves the row is always "one merged stone + the untouched tail". A move that absorbs everything up to original index i scores exactly prefix[i], the prefix sum of stones 0..i, and leaves the game in the state "next player must take a prefix ending at some index > i".

So define dp[i] = the best score difference (current player minus opponent) achievable when the next move must end at index i or later. The current player can either stop the recursion by taking exactly up to i — scoring prefix[i] and then facing -dp[i+1] from the opponent — or push the choice further right, value dp[i+1].

That gives dp[i] = max(dp[i+1], prefix[i] - dp[i+1]). The subtraction flips the sign because it becomes the opponent's turn after this move.

The very first valid ending index from the right is the last stone (you must take at least 2 stones, and the final mandatory move sweeps the whole array), so the base case is dp[n-1] = prefix[n-1]. We then scan i from n-2 down to 1 and keep a single rolling best — no array needed.

Example: stones = [-1,2,-3,4,-5] has prefix sums [-1,1,-2,2,-3]. Rolling the recurrence right-to-left yields 5 as Alice's optimal score difference.

Time: O(n) Space: O(n)