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 thescore difference between Alice and Bob if they both play optimally.

Examples

Example 1

1
2
3
4
5
6
7
8

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

1
2
3
4
5
6

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

1
2
3
4
5
6

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 <= 10^5
  • -10^4 <= stones[i] <= 10^4

Solution

Method 1 - Prefix Sums and Dynamic Programming

Intuition

After the first move, the game reduces to a sequence of prefix sums. At each step, the player can choose to take the first k stones (k ≥ 2), sum them, and replace them with a single stone. The optimal strategy is to maximize the difference using DP from the end.

Approach

  • Compute prefix sums of the stones.
  • Let dp[i] be the maximum score difference Alice can achieve if there are i stones left (after at least one move).
  • dp[i] = max(dp[i+1], prefix[i] - dp[i+1]) for i from n-1 down to 2.
  • The answer is dp[2].

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
    int stoneGameVIII(vector<int>& stones) {
        int n = stones.size();
        vector<int> prefix(n);
        prefix[0] = stones[0];
        for (int i = 1; i < n; ++i) prefix[i] = prefix[i-1] + stones[i];
        int dp = prefix[n-1];
        for (int i = n-2; i >= 1; --i) {
            dp = max(dp, prefix[i] - dp);
        }
        return dp;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

func stoneGameVIII(stones []int) int {
    n := len(stones)
    prefix := make([]int, n)
    prefix[0] = stones[0]
    for i := 1; i < n; i++ {
        prefix[i] = prefix[i-1] + stones[i]
    }
    dp := prefix[n-1]
    for i := n-2; i >= 1; i-- {
        if prefix[i]-dp > dp {
            dp = prefix[i]-dp
        }
        if prefix[i]-dp < dp {
            dp = max(dp, prefix[i]-dp)
        }
        dp = max(dp, prefix[i]-dp)
    }
    return dp
}
func max(a, b int) int { if a > b { return a } else { return b } }
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

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 dp = prefix[n-1];
        for (int i = n-2; i >= 1; i--) {
            dp = Math.max(dp, prefix[i] - dp);
        }
        return dp;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

fun stoneGameVIII(stones: IntArray): Int {
    val n = stones.size
    val prefix = IntArray(n)
    prefix[0] = stones[0]
    for (i in 1 until n) prefix[i] = prefix[i-1] + stones[i]
    var dp = prefix[n-1]
    for (i in n-2 downTo 1) {
        dp = maxOf(dp, prefix[i] - dp)
    }
    return dp
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

def stoneGameVIII(stones: list[int]) -> int:
    n = len(stones)
    prefix = [0]*n
    prefix[0] = stones[0]
    for i in range(1, n):
        prefix[i] = prefix[i-1] + stones[i]
    dp = prefix[-1]
    for i in range(n-2, 0, -1):
        dp = max(dp, prefix[i] - dp)
    return dp
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

pub fn stone_game_viii(stones: Vec<i32>) -> i32 {
    let n = stones.len();
    let mut prefix = vec![0; n];
    prefix[0] = stones[0];
    for i in 1..n {
        prefix[i] = prefix[i-1] + stones[i];
    }
    let mut dp = prefix[n-1];
    for i in (1..n-1).rev() {
        dp = dp.max(prefix[i] - dp);
    }
    dp
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

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

Complexity

  • ⏰ Time complexity: O(n)
  • 🧺 Space complexity: O(n)