349. Stone Game V

dp[i][j] = the most Alice can score from the stones in [i..j]. She picks a split k; Bob discards the heavier half, Alice scores the lighter half's sum and recurses into it. Try every split, keep the max; solve short intervals before long ones.

One value per surviving segment

At any point the game is played on a contiguous segment stoneValue[i..j]. Let dp[i][j] = the maximum total score Alice can still earn starting from that segment. A single stone can't be split, so dp[i][i] = 0.

The recurrence

Alice chooses a split index k (left = [i..k], right = [k+1..j]), then Bob throws away the heavier half. Let L = sum(i..k) and R = sum(k+1..j):

• L < R: Bob discards the right, Alice scores L now and continues on the left: L + dp[i][k].
• L > R: Bob discards the left, Alice scores R and continues on the right: R + dp[k+1][j].
• L == R: Alice chooses the better side: max(L + dp[i][k], R + dp[k+1][j]).

Take the best over all splits:

dp[i][j] = max over k in [i, j-1] of (the value above)

Use a prefix-sum array for O(1) segment sums, and fill intervals by increasing length so both halves are ready. The answer is dp[0][n-1].

Worked example

stoneValue = [6, 2, 3, 4, 5, 5] (total 25).

All length-1 intervals are 0. Building up, the optimal first split for the full row keeps a balanced side that Alice can keep milking. Working the table bottom-up yields dp[0][5] = 18 — Alice's best achievable total.

(For intuition on a smaller case, [1, 2]: only split is L=1, R=2, Bob discards the right, Alice scores 1 → dp = 1.)

Complexity

• Time: O(n^3) — O(n^2) intervals, each scanning up to n split points. (This can be pushed to O(n^2) with a smarter running best, but the cubic version is the clearest.)
• Space: O(n^2) for the interval table.

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];
        }
        // dp[i][j] = max score Alice can still earn from the segment [i..j].
        int[][] dp = new int[n][n];
        for (int length = 2; length <= n; length++) {
            for (int i = 0; i + length - 1 < n; i++) {
                int j = i + length - 1;
                int best = 0;
                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) {
                        best = Math.max(best, left + dp[i][k]);
                    } else if (left > right) {
                        best = Math.max(best, right + dp[k + 1][j]);
                    } else {
                        best = Math.max(best, Math.max(left + dp[i][k], right + dp[k + 1][j]));
                    }
                }
                dp[i][j] = best;
            }
        }
        return dp[0][n - 1];
    }
}