Talentd
For employersSign in
JobsInternshipsPracticeResume toolsCompaniesArticles
For employers
FleetCode
Make and follow sheets.Sign in

Stone Game VIII solution and explanation

HardArrayDynamic ProgrammingGame TheoryMath9 min read75.2% acceptanceUpdated 9 Apr 2026
Asked atInfosys
Practise Stone Game VIII
17:25
花花酱 LeetCode 1872. Stone Game VIII - 刷题找工作 EP394Hua Hua · 17:25 · 4K viewsWatch on YouTube
8 more videos on this problem
  1. 花花酱 LeetCode 1872. Stone Game VIII - 刷题找工作 EP394Hua Hua · 17:25 · 4K views
  2. LeetCode 1872. Stone Game VIIIHappy Coding · 23:25 · 1K views
  3. 1872. Stone Game VIII | LEETCODE WEEKLY CONTEST 242 | DYNAMIC PROGRAMMING | LEETCODEcode Explainer · 13:20 · 1K views
  4. LeetCode Weekly Contest 242 Question 4: Stone Game VIIICoding Ninjas Webinars and Contest Editorials · 23:33 · 1K views
  5. 1872. Stone Game VIII (Leetcode Hard)Programming Live with Larry · 36:38 · 828 views
  6. 【每日一题】1872. Stone Game VIII, 5/28/2021Huifeng Guan · 23:24 · 505 views
  7. Leetcode 1872. Stone Game VIIIFearless Learner · 34:20 · 173 views
  8. LeetCode 1872. Stone Game VIIIRyan Ivy · 43:51 · 74 views
  9. LeetCode 1872: Stone Game VIIIAlitaCode · 28:07 · 8 views

The problem

Alice and Bob take turns playing a game, with Alice starting first.

There are n stones arranged in a row. On each player's turn, while the number of stones is more than one, they will do the following:

  1. Choose an integer x > 1, and remove the leftmost x stones from the row.
  2. Add the sum of the removed stones' values to the player's score.
  3. Place a new stone, whose value is equal to that sum, on the left side of the row.

The game stops when only one stone is left in the row.

The score difference between Alice and Bob is (Alice's score - Bob's score). Alice's goal is to maximize the score difference, and Bob's goal is the minimize the score difference.

Given an integer array stones of length n where stones[i] represents the value of the ith stone from the left, return the score difference between Alice and Bob if they both play optimally.

Example 1:

Input: stones = [-1,2,-3,4,-5]
Output: 5
Explanation:
- Alice removes the first 4 stones, adds (-1) + 2 + (-3) + 4 = 2 to her score, and places a stone of
  value 2 on the left. stones = [2,-5].
- Bob removes the first 2 stones, adds 2 + (-5) = -3 to his score, and places a stone of value -3 on
  the left. stones = [-3].
The difference between their scores is 2 - (-3) = 5.

Example 2:

Input: stones = [7,-6,5,10,5,-2,-6]
Output: 13
Explanation:
- Alice removes all stones, adds 7 + (-6) + 5 + 10 + 5 + (-2) + (-6) = 13 to her score, and places a
  stone of value 13 on the left. stones = [13].
The difference between their scores is 13 - 0 = 13.

Example 3:

Input: stones = [-10,-12]
Output: -22
Explanation:
- Alice can only make one move, which is to remove both stones. She adds (-10) + (-12) = -22 to her
  score and places a stone of value -22 on the left. stones = [-22].
The difference between their scores is (-22) - 0 = -22.

Constraints:

  • n == stones.length
  • 2 <= n <= 105
  • -104 <= stones[i] <= 104

Approach overview

Problem Overview: You are given an integer array where two players take turns removing stones from the left and adding the removed stones' sum to their score. Each move must remove at least two stones. Both players play optimally, and the goal is to compute the maximum score difference the first player can achieve.

This problem mixes array manipulation with optimal play strategy from game theory. The key observation is that once stones are removed, the remaining prefix sums determine the score impact of each move. Efficient solutions rely on prefix sum preprocessing and dynamic programming.

Approach 1: Dynamic Programming with Suffix Sums (O(n) time, O(n) space)

Start by computing a prefix sum array where prefix[i] represents the total of the first i+1 stones. When a player removes the first i+1 stones, they gain prefix[i] points and the game continues with the remaining suffix. Define a DP array dp[i] representing the best score difference the current player can achieve starting from position i. Iterate from right to left. For each index, choose between taking the current prefix or skipping to a later position. The recurrence becomes dp[i] = max(dp[i+1], prefix[i] - dp[i+1]). This works because the opponent will also play optimally, so their best outcome reduces the current player’s advantage. The approach runs in O(n) time with O(n) additional memory for the DP array.

Approach 2: Optimized Dynamic Programming (O(n) time, O(1) space)

The DP recurrence only depends on the next state, which means the entire DP array is unnecessary. Maintain a single variable representing the best score difference seen so far while iterating backward through the prefix sums. Start with the total prefix sum at the end and update the best value using the same transition best = max(best, prefix[i] - best). This preserves the same game-state logic but compresses the DP state into one variable. The algorithm still scans the array once after computing prefix sums, so the time complexity stays O(n) while space drops to O(1). This is the version typically used in competitive programming and production solutions.

Recommended for interviews: The optimized dynamic programming approach is what interviewers usually expect. Building the prefix sum and deriving the recurrence shows understanding of how score differences propagate in adversarial games. Mentioning the full DP array first demonstrates the reasoning process, then reducing it to O(1) space shows strong optimization skills.

Approach 1: Approach 1: Dynamic Programming with Suffix Sums

This approach leverages dynamic programming and suffix sum calculations. We start by calculating the suffix sum for each stone position, which gives the sum of all stones from that position to the end. Our goal is to maximize the score difference Alice can achieve taking turns optimally with Bob. We will use a dp array to track the maximum result from each position onward.

def stoneGameVIII(stones):
    n = len(stones)
    suffix_sum = [0] * n
    suffix_sum[-1] = stones[-1]
    for i in range(n-2, -1, -1):
        suffix_sum[i] = suffix_sum[i+1] + stones[i]
    
    dp = [0] * n
    dp[-2] = suffix_sum[-1]
    
    for i in range(n-3, -1, -1):
        dp[i] = max(suffix_sum[i+1], dp[i+1] + stones[i+1])

    return dp[0]
class Solution {
    public int stoneGameVIII(int[] stones) {
        int n = stones.length;
        int[] suffix_sum = new int[n];
        suffix_sum[n-1] = stones[n-1];
        for (int i = n-2; i >= 0; i--) {
            suffix_sum[i] = suffix_sum[i+1] + stones[i];
        }
        
        int[] dp = new int[n];
        dp[n-2] = suffix_sum[n-1];
        
        for (int i = n-3; i >= 0; i--) {
            dp[i] = Math.max(suffix_sum[i+1], dp[i+1] + stones[i+1]);
        }
        return dp[0];
    }
}
#include <vector>
#include <algorithm>
using namespace std;

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

    vector<int> dp(n, 0);
    dp[n-2] = suffix_sum[n-1];

    for (int i=n-3; i>=0; --i) {
        dp[i] = max(suffix_sum[i+1], dp[i+1] + stones[i+1]);
    }
    return dp[0];
}
function stoneGameVIII(stones) {
    const n = stones.length;
    const suffix_sum = Array(n).fill(0);
    suffix_sum[n-1] = stones[n-1];
    for (let i = n-2; i >= 0; i--) {
        suffix_sum[i] = suffix_sum[i+1] + stones[i];
    }

    const dp = Array(n).fill(0);
    dp[n-2] = suffix_sum[n-1];

    for (let i = n-3; i >= 0; i--) {
        dp[i] = Math.max(suffix_sum[i+1], dp[i+1] + stones[i+1]);
    }

    return dp[0];
}
#include <stdio.h>
#include <stdlib.h>

int stoneGameVIII(int* stones, int stonesSize) {
    int* suffix_sum = (int*)malloc(stonesSize * sizeof(int));
    suffix_sum[stonesSize - 1] = stones[stonesSize - 1];
    for(int i = stonesSize - 2; i >= 0; --i) {
        suffix_sum[i] = suffix_sum[i + 1] + stones[i];
    }
    
    int* dp = (int*)malloc(stonesSize * sizeof(int));
    dp[stonesSize - 2] = suffix_sum[stonesSize - 1];
    
    for(int i = stonesSize - 3; i >= 0; --i) {
        dp[i] = (suffix_sum[i + 1] > dp[i + 1] + stones[i + 1]) ? suffix_sum[i + 1] : (dp[i + 1] + stones[i + 1]);
    }

    int result = dp[0];
    free(suffix_sum);
    free(dp);
    return result;
}
using System;

public class Solution {
    public int StoneGameVIII(int[] stones) {
        int n = stones.Length;
        int[] suffix_sum = new int[n];
        suffix_sum[n-1] = stones[n-1];
        for (int i = n-2; i >= 0; i--) {
            suffix_sum[i] = suffix_sum[i+1] + stones[i];
        }
        
        int[] dp = new int[n];
        dp[n-2] = suffix_sum[n-1];

        for (int i = n-3; i >= 0; i--) {
            dp[i] = Math.Max(suffix_sum[i+1], dp[i+1] + stones[i+1]);
        }
        return dp[0];
    }
}

The solution defines a stoneGameVIII function that calculates the suffix sum of the given stone array from the end to the beginning. Next, it initializes a dp array to keep track of the maximum differences from each position onward. The final result, dp[0], is the answer returned.

Complexity

Time Complexity: O(n), where n is the length of the stones array, because we iterate over the array twice.
Space Complexity: O(n), for storing the suffix sums and the dp array.

Try this approach in the editor

Approach 2: Approach 2: Optimized Dynamic Programming

This approach tries to optimize the space complexity of the earlier approach by eliminating the need to store the entire dp array. Instead, we can maintain just the current and previous values needed to make the decision. This reduces the space needed significantly while maintaining accuracy.

def stoneGameVIII(stones):
    n = len(stones)
    suffix_sum = [0] * n
    suffix_sum[-1] = stones[-1]
    for i in range(n-2, -1, -1):
        suffix_sum[i] = suffix_sum[i+1] + stones[i]

    max_diff = suffix_sum[-1]

    for i in range(n-3, -1, -1):
        max_diff = max(suffix_sum[i+1], max_diff + stones[i+1])

    return max_diff
class Solution {
    public int stoneGameVIII(int[] stones) {
        int n = stones.length;
        int[] suffix_sum = new int[n];
        suffix_sum[n-1] = stones[n-1];
        for (int i = n-2; i >= 0; i--) {
            suffix_sum[i] = suffix_sum[i+1] + stones[i];
        }

        int max_diff = suffix_sum[n-1];

        for (int i = n-3; i >= 0; i--) {
            max_diff = Math.max(suffix_sum[i+1], max_diff + stones[i+1]);
        }

        return max_diff;
    }
}
#include <vector>
#include <algorithm>
using namespace std;

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

    int max_diff = suffix_sum[n-1];

    for (int i = n-3; i >= 0; --i) {
        max_diff = max(suffix_sum[i+1], max_diff + stones[i+1]);
    }

    return max_diff;
}
function stoneGameVIII(stones) {
    const n = stones.length;
    const suffix_sum = Array(n).fill(0);
    suffix_sum[n-1] = stones[n-1];
    for (let i = n-2; i >= 0; i--) {
        suffix_sum[i] = suffix_sum[i+1] + stones[i];
    }

    let max_diff = suffix_sum[n-1];

    for (let i = n-3; i >= 0; i--) {
        max_diff = Math.max(suffix_sum[i+1], max_diff + stones[i+1]);
    }

    return max_diff;
}
#include <stdio.h>
#include <stdlib.h>

int stoneGameVIII(int* stones, int stonesSize) {
    int* suffix_sum = (int*)malloc(stonesSize * sizeof(int));
    suffix_sum[stonesSize - 1] = stones[stonesSize - 1];
    for(int i = stonesSize - 2; i >= 0; --i) {
        suffix_sum[i] = suffix_sum[i + 1] + stones[i];
    }
    
    int max_diff = suffix_sum[stonesSize - 1];

    for(int i = stonesSize - 3; i >= 0; --i) {
        max_diff = (suffix_sum[i + 1] > max_diff + stones[i + 1]) ? suffix_sum[i + 1] : (max_diff + stones[i + 1]);
    }

    free(suffix_sum);
    return max_diff;
}
using System;

public class Solution {
    public int StoneGameVIII(int[] stones) {
        int n = stones.Length;
        int[] suffix_sum = new int[n];
        suffix_sum[n-1] = stones[n-1];
        for (int i = n-2; i >= 0; i--) {
            suffix_sum[i] = suffix_sum[i+1] + stones[i];
        }

        int max_diff = suffix_sum[n-1];

        for (int i = n-3; i >= 0; i--) {
            max_diff = Math.Max(suffix_sum[i+1], max_diff + stones[i+1]);
        }

        return max_diff;
    }
}

By keeping track of only the maximum difference, rather than an entire array of results, this Python function improves on space efficiency. The max_diff variable holds the optimal value from the end toward the start.

Complexity

Time Complexity: O(n).
Space Complexity: O(1), since we no longer need the full dp array.

Try this approach in the editor

Approach 3: Prefix Sum + Memoization Search

According to the problem description, each time we take the leftmost x stones, add their sum to our score, and then put a stone with this sum value on the leftmost side, it is equivalent to merging these x stones into a stone with this sum value, and the prefix sum remains unchanged.

We can use a prefix sum array s of length n to represent the prefix sum of the array stones, where s[i] represents the sum of the elements stones[0..i].

Next, we design a function dfs(i), which means that we currently take stones from stones[i:], and return the maximum score difference that the current player can get.

The execution process of the function dfs(i) is as follows:

  • If i geq n - 1, it means that we can only take all the stones at present, so we return s[n - 1].
  • Otherwise, we can choose to take all the stones from stones[i + 1:], and the score difference obtained is dfs(i + 1); we can also choose to take the stones stones[:i], and the score difference obtained is s[i] - dfs(i + 1). We take the maximum of the two situations, which is the maximum score difference that the current player can get.

Finally, we can get the score difference between Alice and Bob as dfs(1), that is, Alice must start the game by taking stones from stones[1:].

To avoid repeated calculations, we can use memoization search.

The time complexity is O(n), and the space complexity is O(n). Here, n is the length of the array stones.

function stoneGameVIII(stones: number[]): number {
    const n = stones.length;
    const f: number[] = Array(n).fill(-1);
    for (let i = 1; i < n; ++i) {
        stones[i] += stones[i - 1];
    }
    const dfs = (i: number): number => {
        if (i >= n - 1) {
            return stones[i];
        }
        if (f[i] === -1) {
            f[i] = Math.max(dfs(i + 1), stones[i] - dfs(i + 1));
        }
        return f[i];
    };
    return dfs(1);
}
func stoneGameVIII(stones []int) int {
	n := len(stones)
	f := make([]int, n)
	for i := range f {
		f[i] = -1
	}
	for i := 1; i < n; i++ {
		stones[i] += stones[i-1]
	}
	var dfs func(int) int
	dfs = func(i int) int {
		if i >= n-1 {
			return stones[i]
		}
		if f[i] == -1 {
			f[i] = max(dfs(i+1), stones[i]-dfs(i+1))
		}
		return f[i]
	}
	return dfs(1)
}
Try this approach in the editor

Approach 4: Prefix Sum + Dynamic Programming

We can also use dynamic programming to solve this problem.

Similar to Solution 1, we first use a prefix sum array s of length n to represent the prefix sum of the array stones, where s[i] represents the sum of the elements stones[0..i].

We define f[i] to represent the maximum score difference that the current player can get when taking stones from stones[i:].

If the player chooses to take the stones stones[:i], then the score obtained is s[i]. At this time, the other player will take stones from stones[i+1:], and the maximum score difference that the other player can get is f[i+1]. Therefore, the maximum score difference that the current player can get is s[i] - f[i+1].

If the player chooses to take stones from stones[i+1:], then the maximum score difference obtained is f[i+1].

Therefore, we can get the state transition equation:

$ f[i] = max{s[i] - f[i+1], f[i+1]}

Finally, we can get the score difference between Alice and Bob as f[1], that is, Alice must start the game by taking stones from stones[1:].

We notice that f[i] is only related to f[i+1], so we only need to use a variable f to represent f[i].

The time complexity is O(n), and the space complexity is O(1). Here, n is the length of the array stones$.

function stoneGameVIII(stones: number[]): number {
    const n = stones.length;
    for (let i = 1; i < n; ++i) {
        stones[i] += stones[i - 1];
    }
    let f = stones[n - 1];
    for (let i = n - 2; i; --i) {
        f = Math.max(f, stones[i] - f);
    }
    return f;
}
Try this approach in the editor

Complexity comparison

ApproachComplexity
Approach 1: Dynamic Programming with Suffix Sums

Time Complexity: O(n), where n is the length of the stones array, because we iterate over the array twice.
Space Complexity: O(n), for storing the suffix sums and the dp array.

Approach 2: Optimized Dynamic Programming

Time Complexity: O(n).
Space Complexity: O(1), since we no longer need the full dp array.

Prefix Sum + Memoization Search–
Prefix Sum + Dynamic Programming–

Complexity analysis

ApproachTimeSpaceWhen to Use
Dynamic Programming with Suffix SumsO(n)O(n)Useful when first deriving the DP transition and explaining the game state clearly
Optimized Dynamic ProgrammingO(n)O(1)Best for production or interviews where memory optimization is expected

Frequently asked questions

Is Stone Game VIII easy or hard?

Stone Game VIII is classified as a Hard problem. The difficulty comes from recognizing the prefix-sum transformation and deriving the correct dynamic programming recurrence for optimal play.

Stone Game VIII Python/Java solution

Implementations typically compute prefix sums and then run a backward DP pass. The same logic works across Python, Java, C++, C, C#, and JavaScript because the algorithm relies only on array traversal and arithmetic operations.

How to solve Stone Game VIII in O(n)?

First compute prefix sums so each move's score can be calculated instantly. Then iterate backward while tracking the best achievable score difference using the relation best = max(best, prefix[i] - best). This dynamic programming transition captures optimal play from both players and finishes in linear time.

What is the best approach for Stone Game VIII?

The best approach uses prefix sums combined with dynamic programming. After computing prefix sums, iterate from right to left and maintain the maximum score difference using the recurrence dp[i] = max(dp[i+1], prefix[i] - dp[i+1]). This reduces the game to a single pass over the array and runs in O(n) time.

Is Stone Game VIII asked at Google/Amazon/Meta?

Hard dynamic programming and game theory problems like Stone Game VIII commonly appear in interviews at large tech companies including Google, Amazon, and Meta. The problem tests prefix sum usage, adversarial reasoning, and DP optimization.

What data structure is used in Stone Game VIII?

The core data structure is a prefix sum array that stores cumulative totals of the stones. Dynamic programming is then applied over these values to simulate optimal moves and compute the best score difference.

What is the time complexity of Stone Game VIII?

The optimal solution runs in O(n) time because the algorithm computes prefix sums once and then scans the array from right to left a single time. The optimized implementation uses O(1) extra space, while a more explicit DP version uses O(n) space.

Comments

Next problem · similarStone GameMedium
Now write it yourselfClose this page and solve Stone Game VIII in the editor, without looking.
Practise Stone Game VIII