Stone game vii

Array Math Dynamic Programming Game Theory

58.7% acceptance

Feb 25, 2026

1047

175

Alice and Bob take turns playing. On each turn, a player removes the leftmost or rightmost stone and receives points equal to the SUM of remaining stones. Alice wants to maximize the score difference, Bob wants to minimize it. Return Alice's score minus Bob's score when both play optimally.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

impl Solution {
  pub fn stone_game_vii(stones: Vec<i32>) -> i32 {
    let n = stones.len();
    // prefix sums
    let mut prefix = vec![0i32; n + 1];
    for i in 0..n {
      prefix[i + 1] = prefix[i] + stones[i];
    }
    let sum = |l: usize, r: usize| -> i32 { prefix[r + 1] - prefix[l] };

    // dp[l][r] = max score diff for current player on [l..r]
    let mut dp = vec![vec![0i32; n]; n];
    // Fill by increasing length
    for len in 2..=n {
      for l in 0..=n - len {
        let r = l + len - 1;
        let take_left = sum(l + 1, r) - dp[l + 1][r];
        let take_right = sum(l, r - 1) - dp[l][r - 1];
        dp[l][r] = take_left.max(take_right);
      }
    }
    dp[0][n - 1]
  }
}