Code Implementation

class Solution:
    def stoneGameVIII(self, stones):
        n = len(stones)
        # Compute prefix sums
        for i in range(1, n):
            stones[i] += stones[i-1]
        # dp[i]: max score Alice can get if there are i stones left
        # We only need to keep track of dp[i+1], so do it backwards
        best = stones[-1]
        for i in range(n-2, 0, -1):
            best = max(best, stones[i] - best)
        return best
      

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

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

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

Problem Description

In the Stone Game VIII problem, you are given an integer array stones representing a row of stones. Alice and Bob play a game in turns, with Alice always going first.

• On each turn, the current player must remove the leftmost at least two stones (so at least the first two stones), sum their values, and replace them with their sum at the front of the array. The new array is then shorter by one stone.
• The game continues until only one stone remains.
• The score for Alice is the sum of all the values she collects after each of her moves, minus the sum of the values Bob collects after his moves.
• Both players play optimally.

Your task is to return the maximum score Alice can achieve over Bob, given the initial stones array.

Key constraints:

• 2 <= stones.length <= 10^5
• -10^4 <= stones[i] <= 10^4
• There is always one valid solution.

Thought Process

At first glance, this problem resembles other classic two-player games where players make optimal choices. The naive approach would be to simulate every possible move sequence, but with up to 10⁵ stones, this is computationally infeasible.

The key insight is to realize that after the first move (removing at least two stones), the leftmost stone is always a prefix sum of the array. Each subsequent move also replaces the leftmost stones with their prefix sum.

Instead of tracking the entire array, we can focus on the prefix sums and use dynamic programming to keep track of the optimal difference Alice can achieve at each stage. The problem then becomes finding, for each possible split, the best score difference for Alice, assuming both play optimally.

The transition from brute-force to optimization comes from recognizing overlapping subproblems and that only the prefix sums matter, not the full array at each step.

Solution Approach

Let’s break down the efficient solution step by step:

1. Prefix Sums: First, compute the prefix sum array for stones. After each move, the new leftmost stone is always a prefix sum.
2. Dynamic Programming: Define dp[i] as the maximum score difference Alice can achieve if there are i stones left (i.e., after making n-i moves).
3. Recurrence: At each step, Alice can choose to stop or continue. The optimal choice is:
   • dp[i] = max(prefix_sum[i] - dp[i+1], dp[i+1])
   This means: Alice can take the current prefix sum minus what Bob can get from the next step, or just stick with the previous best.
4. Reverse Traversal: Since the last move is forced, we can process the prefix sums from the end towards the start, updating the best score difference at each step.
5. Space Optimization: Since only the previous best is needed, we can use a single variable instead of a full DP array.

This approach ensures we only make a single pass over the array, yielding an efficient solution.

Example Walkthrough

Consider the input stones = [-1, 2, -3, 4, -5].

1. Compute prefix sums:
   • [-1, 1, -2, 2, -3]
2. Start from the end:
   • Initialize best = -3 (prefix_sum[4])
   • i = 3: best = max(2 - (-3), -3) = max(5, -3) = 5
   • i = 2: best = max(-2 - 5, 5) = max(-7, 5) = 5
   • i = 1: best = max(1 - 5, 5) = max(-4, 5) = 5
3. Return 5 as the answer. This is the maximum difference Alice can achieve over Bob.

This shows how, at each step, we consider the best possible outcome for Alice, assuming both play optimally.

Time and Space Complexity

Brute-force approach: If we tried all possible sequences, the time complexity would be exponential, as each move can split the array in different ways.

Optimized approach:

• Time Complexity: O(n), where n is the length of stones. We compute prefix sums in one pass and process the DP in another pass.
• Space Complexity: O(1) extra space (or O(n) if storing the prefix sums, but this can be done in-place).

Summary

The Stone Game VIII problem is a classic example of reducing a two-player game to a dynamic programming problem by focusing on prefix sums and optimal substructure. The key insight is that after each move, the game state can be represented by a prefix sum, allowing us to use a simple recurrence to compute the best possible outcome for Alice. The final algorithm is both elegant and efficient, running in linear time with minimal extra space.