366. Stone Game VIII

A move that removes the leftmost x stones and replaces them by their sum is exactly a choice of a prefix boundary — the merged left stone is always the running prefix sum. So each turn a player just picks an index i (i >= 1) and scores prefix[i]; the opponent then continues from i. Play the minimax over prefix boundaries right-to-left.

Key reframing

The rules look complicated, but notice what a move actually does: you remove the leftmost x stones, add their sum to your score, and drop a new stone equal to that sum back on the left. That new stone is precisely the prefix sum of everything removed. So after any sequence of moves the leftmost stone always equals prefix[i] for some boundary i.

That means a turn is simply: pick a boundary i (with i >= 1, since x > 1) and score prefix[i]. The stones to the right (i+1 .. n-1) are untouched, and it becomes the opponent's turn facing the same kind of choice starting at i.

Let prefix[i] = stones[0] + stones[1] + ... + stones[i].

The DP

Let dp[i] = the best score difference (current player minus opponent) the player to move can guarantee, given they may choose any boundary >= i.

Processing right-to-left:

• Base: dp[n-1] = prefix[n-1]. At the last boundary the only move left is to take everything, scoring the full sum, with no reply.

• Transition: at boundary i the player either

  • takes now: scores prefix[i], then the opponent optimally gets dp[i+1] in their favor, so the net difference is prefix[i] - dp[i+1]; or
  • waits: defers to a later boundary, keeping dp[i+1].

  Take the better of the two: dp[i] = max(dp[i+1], prefix[i] - dp[i+1]).

The answer is dp[1] — Alice's first move must remove more than one stone, so the earliest boundary she can pick is index 1. Because each dp[i] only depends on dp[i+1], we collapse the table to a single rolling scalar → O(1) extra space.

Worked example

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

Prefix sums: prefix = [-1, 1, -2, 2, -3].

Scan right-to-left:

1. dp = prefix[4] = -3 (base: forced to take all).
2. i = 3: max(dp, prefix[3] - dp) = max(-3, 2 - (-3)) = max(-3, 5) = 5.
3. i = 2: max(5, prefix[2] - 5) = max(5, -2 - 5) = max(5, -7) = 5.
4. i = 1: max(5, prefix[1] - 5) = max(5, 1 - 5) = max(5, -4) = 5.

Answer = dp = 5, matching the game: Alice removes the first 4 stones (+2), Bob is forced to take both remaining (-3), difference 2 - (-3) = 5.

Complexity

• Time: O(n) — one prefix-sum pass plus one right-to-left DP pass.
• Space: O(1) beyond the prefix array (a single rolling dp scalar).

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];
        }
        // dp = best score difference the player to move can guarantee,
        // scanning boundaries from right to left. Base: must take everything.
        int dp = prefix[n - 1];
        for (int i = n - 2; i >= 1; i--) {
            dp = Math.max(dp, prefix[i] - dp);
        }
        return dp;
    }
}