1872. Stone Game VIII LeetCode Solution

Last updated: February 25, 2025

In this guide, you will get 1872. Stone Game VIII LeetCode Solution with the best time and space complexity. The solution to Stone Game VIII problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Stone Game VIII solution in C++
Stone Game VIII solution in Java
Stone Game VIII solution in Python
Additional Resources

1872. Stone Game VIII LeetCode Solution image

Problem Statement of Stone Game VIII

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:

Choose an integer x > 1, and remove the leftmost x stones from the row.
Add the sum of the removed stones’ values to the player’s score.
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

Complexity Analysis

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

1872. Stone Game VIII LeetCode Solution in C++

class Solution {
 public:
  int stoneGameVIII(vector<int>& stones) {
    const int n = stones.size();
    vector<int> prefix(n);
    // dp[i] := the maximum score difference the current player can get when the
    // game starts at i, i.e. stones[0..i] are merged into the value prefix[i]
    vector<int> dp(n, INT_MIN);

    partial_sum(stones.begin(), stones.end(), prefix.begin());

    // Must take all when there're only two stones left.
    dp[n - 2] = prefix.back();

    for (int i = n - 3; i >= 0; --i)
      dp[i] = max(dp[i + 1], prefix[i + 1] - dp[i + 1]);

    return dp[0];
  }
};
/* code provided by PROGIEZ */

1872. Stone Game VIII LeetCode Solution in Java

class Solution {
  public int stoneGameVIII(int[] stones) {
    final int n = stones.length;
    int[] prefix = stones.clone();
    // dp[i] := the maximum score difference the current player can get when the
    // game starts at i, i.e. stones[0..i] are merged into the value prefix[i]
    int[] dp = new int[n];
    Arrays.fill(dp, Integer.MIN_VALUE);

    for (int i = 1; i < prefix.length; ++i)
      prefix[i] += prefix[i - 1];

    // Must take all when there're only two stones left.
    dp[n - 2] = prefix[n - 1];

    for (int i = n - 3; i >= 0; --i)
      dp[i] = Math.max(dp[i + 1], prefix[i + 1] - dp[i + 1]);

    return dp[0];
  }
}
// code provided by PROGIEZ

1872. Stone Game VIII LeetCode Solution in Python

class Solution:
  def stoneGameVIII(self, stones: list[int]) -> int:
    n = len(stones)
    prefix = list(itertools.accumulate(stones))
    # dp[i] := the maximum score difference the current player can get when the
    # game starts at i, i.e. stones[0..i] are merged into the value prefix[i]
    dp = [-math.inf] * n

    # Must take all when there're only two stones left.
    dp[n - 2] = prefix[-1]

    for i in reversed(range(n - 2)):
      dp[i] = max(dp[i + 1], prefix[i + 1] - dp[i + 1])

    return dp[0]
 # code by PROGIEZ

Additional Resources

Happy Coding! Keep following PROGIEZ for more updates and solutions.

Table of Contents