359. Stone Game VII

dp[i][j] = the best score DIFFERENCE (mover minus opponent) on the sub-row stones[i..j]. Removing an end scores the sum of what stays and hands that smaller row to the opponent, whose lead subtracts. Prefix sums give the remaining sum in O(1); fill short rows first.

Track the difference, not two scores

Because every point Bob scores directly narrows Alice's lead, collapse the game into one number: dp[i][j] = the best score difference (the player to move, minus the other) achievable when only stones[i..j] remain.

The recurrence

When you remove an end stone you score the sum of the stones that stay. Let sum(a..b) be a prefix-sum lookup:

• Remove the left stone i: the remaining row is stones[i+1..j], so you score sum(i+1..j); then the opponent plays that row and guarantees dp[i+1][j]. Net: sum(i+1..j) - dp[i+1][j].
• Remove the right stone j: by symmetry, sum(i..j-1) - dp[i][j-1].

Alice-to-move maximizes; the subtraction already encodes Bob minimizing. Keep the larger:

dp[i][j] = max( sum(i+1..j) - dp[i+1][j],  sum(i..j-1) - dp[i][j-1] )

Base: dp[i][i] = 0 — one stone left, removing it leaves an empty row worth 0.

Fill by increasing sub-row length. The answer is dp[0][n-1].

Worked example

stones = [5, 3, 1, 4, 2], prefix sums make any range sum O(1).

Length-2:

• dp[0][1]: remove left → sum(1..1)=3; remove right → sum(0..0)=5. max(3, 5) = 5.
• dp[1][2] = max(1, 3) = 3; dp[2][3] = max(4, 1) = 4; dp[3][4] = max(2, 4) = 4.

Length-3:

• dp[0][2]: remove left → sum(1..2)=4 - dp[1][2]=3 → 1; remove right → sum(0..1)=8 - dp[0][1]=5 → 3. dp[0][2] = 3.
• similarly dp[1][3] = 4, dp[2][4] = 3.

Continuing through lengths 4 and 5 gives dp[0][4] = 6.

So with optimal play the score difference is 6.

Complexity

• Time: O(n^2) — one pass over every sub-row.
• Space: O(n^2) for the table (reducible to O(n)).

class Solution {
    public int stoneGameVII(int[] stones) {
        int n = stones.length;
        int[] prefix = new int[n + 1];
        for (int i = 0; i < n; i++) {
            prefix[i + 1] = prefix[i] + stones[i];
        }
        // dp[i][j] = best score difference (mover - opponent) on stones[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 removeLeft = (prefix[j + 1] - prefix[i + 1]) - dp[i + 1][j];
                int removeRight = (prefix[j] - prefix[i]) - dp[i][j - 1];
                dp[i][j] = Math.max(removeLeft, removeRight);
            }
        }
        return dp[0][n - 1];
    }
}