Stone Game V
HardUpdated: Aug 2, 2025
Practice on:
Problem
There are several stones arranged in a row, and each stone has an associated value which is an integer given in the array stoneValue.
In each round of the game, Alice divides the row into two non-empty rows (i.e. left row and right row), then Bob calculates the value of each row which is the sum of the values of all the stones in this row. Bob throws away the row which has the maximum value, and Alice's score increases by the value of the remaining row. If the value of the two rows are equal, Bob lets Alice decide which row will be thrown away. The next round starts with the remaining row.
The game ends when there is only one stone remaining. Alice's score is initially zero.
Return the maximum score that Alice can obtain.
Examples
Example 1
Input: stoneValue = [6,2,3,4,5,5]
Output: 18
Explanation: In the first round, Alice divides the row to [6,2,3], [4,5,5]. The left row has the value 11 and the right row has value 14. Bob throws away the right row and Alice's score is now 11.
In the second round Alice divides the row to [6], [2,3]. This time Bob throws away the left row and Alice's score becomes 16 (11 + 5).
The last round Alice has only one choice to divide the row which is [2], [3]. Bob throws away the right row and Alice's score is now 18 (16 + 2). The game ends because only one stone is remaining in the row.
Example 2
Input: stoneValue = [7,7,7,7,7,7,7]
Output: 28
Example 3
Input: stoneValue = [4]
Output: 0
Constraints
1 <= stoneValue.length <= 5001 <= stoneValue[i] <= 106
Solution
Method 1 – Dynamic Programming with Prefix Sums
Intuition
We can use DP to solve for the maximum score Alice can get for every subarray. Prefix sums allow us to quickly compute the sum of any interval, and we try all possible splits to maximize Alice's score.
Approach
- Precompute prefix sums for quick range sum queries.
- Use a DP table
dp[i][j]for the max score Alice can get fromstoneValue[i..j]. - For each interval, try every split point and update the DP value based on the rules.
- The answer is
dp[0][n-1].
Code
C++
class Solution {
public:
int stoneGameV(vector<int>& stoneValue) {
int n = stoneValue.size();
vector<int> prefix(n+1);
for (int i = 0; i < n; ++i) prefix[i+1] = prefix[i] + stoneValue[i];
vector<vector<int>> dp(n, vector<int>(n));
for (int len = 2; len <= n; ++len) {
for (int i = 0; i + len <= n; ++i) {
int j = i + len - 1;
for (int k = i; k < j; ++k) {
int left = prefix[k+1] - prefix[i];
int right = prefix[j+1] - prefix[k+1];
if (left < right)
dp[i][j] = max(dp[i][j], left + dp[i][k]);
else if (left > right)
dp[i][j] = max(dp[i][j], right + dp[k+1][j]);
else
dp[i][j] = max(dp[i][j], left + max(dp[i][k], dp[k+1][j]));
}
}
}
return dp[0][n-1];
}
};
Go
func stoneGameV(stoneValue []int) int {
n := len(stoneValue)
prefix := make([]int, n+1)
for i := 0; i < n; i++ { prefix[i+1] = prefix[i] + stoneValue[i] }
dp := make([][]int, n)
for i := range dp { dp[i] = make([]int, n) }
for l := 2; l <= n; l++ {
for i := 0; i+l <= n; i++ {
j := i + l - 1
for k := i; k < j; k++ {
left := prefix[k+1] - prefix[i]
right := prefix[j+1] - prefix[k+1]
if left < right {
if dp[i][j] < left+dp[i][k] { dp[i][j] = left+dp[i][k] }
} else if left > right {
if dp[i][j] < right+dp[k+1][j] { dp[i][j] = right+dp[k+1][j] }
} else {
v := left + max(dp[i][k], dp[k+1][j])
if dp[i][j] < v { dp[i][j] = v }
}
}
}
}
return dp[0][n-1]
}
func max(a, b int) int { if a > b { return a }; return b }
Java
class Solution {
public int stoneGameV(int[] stoneValue) {
int n = stoneValue.length;
int[] prefix = new int[n+1];
for (int i = 0; i < n; ++i) prefix[i+1] = prefix[i] + stoneValue[i];
int[][] dp = new int[n][n];
for (int len = 2; len <= n; ++len) {
for (int i = 0; i + len <= n; ++i) {
int j = i + len - 1;
for (int k = i; k < j; ++k) {
int left = prefix[k+1] - prefix[i];
int right = prefix[j+1] - prefix[k+1];
if (left < right)
dp[i][j] = Math.max(dp[i][j], left + dp[i][k]);
else if (left > right)
dp[i][j] = Math.max(dp[i][j], right + dp[k+1][j]);
else
dp[i][j] = Math.max(dp[i][j], left + Math.max(dp[i][k], dp[k+1][j]));
}
}
}
return dp[0][n-1];
}
}
Kotlin
class Solution {
fun stoneGameV(stoneValue: IntArray): Int {
val n = stoneValue.size
val prefix = IntArray(n+1)
for (i in 0 until n) prefix[i+1] = prefix[i] + stoneValue[i]
val dp = Array(n) { IntArray(n) }
for (len in 2..n) {
for (i in 0..n-len) {
val j = i + len - 1
for (k in i until j) {
val left = prefix[k+1] - prefix[i]
val right = prefix[j+1] - prefix[k+1]
if (left < right)
dp[i][j] = maxOf(dp[i][j], left + dp[i][k])
else if (left > right)
dp[i][j] = maxOf(dp[i][j], right + dp[k+1][j])
else
dp[i][j] = maxOf(dp[i][j], left + maxOf(dp[i][k], dp[k+1][j]))
}
}
}
return dp[0][n-1]
}
}
Python
class Solution:
def stoneGameV(self, stoneValue: list[int]) -> int:
n = len(stoneValue)
prefix = [0]*(n+1)
for i in range(n):
prefix[i+1] = prefix[i] + stoneValue[i]
dp = [[0]*n for _ in range(n)]
for l in range(2, n+1):
for i in range(n-l+1):
j = i + l - 1
for k in range(i, j):
left = prefix[k+1] - prefix[i]
right = prefix[j+1] - prefix[k+1]
if left < right:
dp[i][j] = max(dp[i][j], left + dp[i][k])
elif left > right:
dp[i][j] = max(dp[i][j], right + dp[k+1][j])
else:
dp[i][j] = max(dp[i][j], left + max(dp[i][k], dp[k+1][j]))
return dp[0][n-1]
Rust
impl Solution {
pub fn stone_game_v(stone_value: Vec<i32>) -> i32 {
let n = stone_value.len();
let mut prefix = vec![0; n+1];
for i in 0..n { prefix[i+1] = prefix[i] + stone_value[i]; }
let mut dp = vec![vec![0; n]; n];
for len in 2..=n {
for i in 0..=n-len {
let j = i + len - 1;
for k in i..j {
let left = prefix[k+1] - prefix[i];
let right = prefix[j+1] - prefix[k+1];
if left < right {
dp[i][j] = dp[i][j].max(left + dp[i][k]);
} else if left > right {
dp[i][j] = dp[i][j].max(right + dp[k+1][j]);
} else {
dp[i][j] = dp[i][j].max(left + dp[i][k].max(dp[k+1][j]));
}
}
}
}
dp[0][n-1]
}
}
TypeScript
class Solution {
stoneGameV(stoneValue: number[]): number {
const n = stoneValue.length;
const prefix = Array(n+1).fill(0);
for (let i = 0; i < n; i++) prefix[i+1] = prefix[i] + stoneValue[i];
const dp = Array.from({length: n}, () => Array(n).fill(0));
for (let len = 2; len <= n; len++) {
for (let i = 0; i + len <= n; i++) {
const j = i + len - 1;
for (let k = i; k < j; k++) {
const left = prefix[k+1] - prefix[i];
const right = prefix[j+1] - prefix[k+1];
if (left < right)
dp[i][j] = Math.max(dp[i][j], left + dp[i][k]);
else if (left > right)
dp[i][j] = Math.max(dp[i][j], right + dp[k+1][j]);
else
dp[i][j] = Math.max(dp[i][j], left + Math.max(dp[i][k], dp[k+1][j]));
}
}
}
return dp[0][n-1];
}
}
Complexity
- ⏰ Time complexity:
O(n^3)wherenis the number of stones. Each interval and split is checked. - 🧺 Space complexity:
O(n^2)for the DP table.