Stone game viii

Array Math Dynamic Programming Prefix Sum Game Theory

53.9% acceptance

Feb 25, 2026

473

Alice and Bob take turns playing a game, with Alice starting first. There are n stones arranged in a row. On each turn, a player chooses x > 1 and removes the leftmost x stones, scoring their sum and placing a new stone of that sum on the left. The game stops when only one stone is left. Return Alice_score - Bob_score if they both play optimally.

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn stone_game_viii(stones: Vec<i32>) -> i32 {
    let n = stones.len();
    // Compute prefix sums
    let mut prefix = vec![0i64; n];
    prefix[0] = stones[0] as i64;
    for i in 1..n {
      prefix[i] = prefix[i - 1] + stones[i] as i64;
    }

    // dp[i] = best score difference (current player - opponent) when
    // current player must pick some j >= i (taking prefix[j]).
    // dp[i] = max(prefix[i] - dp[i+1], dp[i+1])
    // = max(prefix[i], dp[i+1] + dp[i+1] - prefix[i])? No.
    // dp[i] = max(prefix[i] - dp[i+1], dp[i+1])

    // Base: dp[n-1] = prefix[n-1]
    let mut dp = prefix[n - 1];
    for i in (1..n - 1).rev() {
      dp = dp.max(prefix[i] - dp);
    }
    dp as i32
  }
}