Get started

Stone Game V — Hard Problem & Solution

Stones are arranged in a row and stone i has the value stoneValue[i]. Alice plays a series of rounds.

Problem statement

Stones are arranged in a row and stone i has the value stoneValue[i].

Alice plays a series of rounds. In each round she splits the current row into two non-empty parts, a left part and a right part. Bob adds up the values of each part and throws away the part with the larger sum; the sum of the part that stays is added to Alice's score. If both parts have the same sum, Alice chooses which one Bob throws away. The kept part becomes the new row.

The game ends when a single stone is left. Alice starts with a score of 0. Return the maximum score she can reach.

Example 1

Input: stoneValue = [2,4,1,3]
Output: 5
Explanation: Split into `[2,4]` and `[1,3]`: Bob discards `[2,4]` (sum 6), Alice scores 4. Then `[1]`|`[3]`: Bob discards `[3]`, Alice scores 1. Total 5.

Example 2

Input: stoneValue = [5,5,4,3,2,6]
Output: 18

Example 3

Input: stoneValue = [9]
Output: 0
Explanation: A single stone ends the game immediately.

Constraints

  • 1 <= stoneValue.length <= 500
  • 1 <= stoneValue[i] <= 10^6

How to solve Stone Game V

The row that survives each round is always a contiguous range of the original, and Alice's future depends only on that range. That makes an interval DP: best(i, j) is the best score from the range, built from shorter ranges.

Approach

  1. Build prefix sums so any range total is O(1).
  2. best(i, i) = 0: one stone ends the game.
  3. For each range [i, j] by increasing length and each split point m in [i, j - 1]: let L = sum(i..m) and R = sum(m+1..j).
  4. If L < R the candidate is L + best(i, m); if L > R it is R + best(m+1, j); if L == R it is L + max(best(i, m), best(m+1, j)).
  5. best(i, j) is the largest candidate. Return best(0, n - 1).

Why it works

Bob's move is forced by the sums, so each split leads to exactly one continuation (two when the sums tie, and Alice picks the better one). Alice's score is the kept sum plus whatever she can make of the kept range, which is exactly best of a strictly shorter range — so filling ranges by length always has the needed values ready, and the maximum over all splits is her optimum.

Complexity

  • Time — O(n^3)
  • Space — O(n^2)

Pitfalls

  • The kept part is the one with the smaller sum, and that smaller sum is what Alice scores.
  • On a tie Alice may keep either part — take the larger continuation, not just one side.
  • Recomputing part sums inside the split loop makes it O(n^4); use prefix sums.

Reference solution

Python

from typing import List

def stoneGameV(stoneValue: List[int]) -> int:
    n = len(stoneValue)
    pre = [0] * (n + 1)
    for i in range(n):
        pre[i + 1] = pre[i] + stoneValue[i]
    best = [[0] * n for _ in range(n)]
    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            top = 0
            for m in range(i, j):
                left = pre[m + 1] - pre[i]
                right = pre[j + 1] - pre[m + 1]
                if left < right:
                    cand = left + best[i][m]
                elif left > right:
                    cand = right + best[m + 1][j]
                else:
                    cand = left + max(best[i][m], best[m + 1][j])
                if cand > top:
                    top = cand
            best[i][j] = top
    return best[0][n - 1]

JavaScript

var stoneGameV = function(stoneValue) {
    var n = stoneValue.length;
    var pre = new Array(n + 1).fill(0);
    for (var i = 0; i < n; i++) pre[i + 1] = pre[i] + stoneValue[i];
    var best = [];
    for (var i = 0; i < n; i++) best.push(new Array(n).fill(0));
    for (var len = 2; len <= n; len++) {
        for (var i = 0; i + len <= n; i++) {
            var j = i + len - 1, top = 0;
            for (var m = i; m < j; m++) {
                var left = pre[m + 1] - pre[i], right = pre[j + 1] - pre[m + 1], cand;
                if (left < right) cand = left + best[i][m];
                else if (left > right) cand = right + best[m + 1][j];
                else cand = left + Math.max(best[i][m], best[m + 1][j]);
                if (cand > top) top = cand;
            }
            best[i][j] = top;
        }
    }
    return best[0][n - 1];
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 988 arrays problems · the whole catalogue

Learn the technique: Arrays · Dynamic Programming