1563. Stone Game V

Array
Dynamic Programming
Prefix Sum
Two Pointers
Game Theory
Interval DP

TIME

O(n^2)

SPACE

O(n^2)

Intuition

Every round leaves Alice with a contiguous subarray, so the state is an interval. Let dp[i][j] = the maximum score obtainable starting from stones i..j. Splitting at k gives left sum L and right sum R; Bob discards the larger, so Alice gains the smaller side and continues on it. On a tie she picks whichever side is better.

dp[i][j] = max over k in [i, j-1] of:
    L < R  ->  L + dp[i][k]
    R < L  ->  R + dp[k+1][j]
    L == R ->  max(L + dp[i][k], R + dp[k+1][j])

That's O(n^3), about 21M split evaluations at n = 500. It can be reduced to O(n^2) by noticing that for a fixed i, the split threshold (where L stops being smaller than R) only moves rightward as j grows, and that the two branch values are prefix/suffix maxima that can be cached.

Approach

Prefix sums give sum(i..j) in O(1). Iterate i from n-1 down to 0, and j from i+1 up, this order makes both dp[i][k] (same i, smaller j) and dp[k+1][j] (larger i) already available.

Maintain two tables:

mL[i][k] = max over k' in [i..k] of (sum(i..k') + dp[i][k']) best value when the left part [i..k'] is kept
mR[k][j] = max over k' in [k..j] of (sum(k'..j) + dp[k'][j]) best value when the right part [k'..j] is kept

For each [i, j], advance a monotone pointer p = the smallest k with 2 * sum(i..k) >= total:

splits k < p keep the left → best is mL[i][p-1]
splits k >= p keep the right → best is mR[p+1][j]
if 2 * sum(i..p) == total exactly, the tie at k = p lets Alice keep either side, so extend the left range to mL[i][p]

Then dp[i][j] = max(left candidate, right candidate), and update mL[i][j], mR[i][j] with the newly computed dp[i][j].

Complexity

Time: O(n^2), the pointer p advances monotonically for each i, so all inner work is amortized O(1)
Space: O(n^2), the dp, mL, mR tables

Edge Cases

Single stone → no split possible → score 0 (Example 3)
All equal values (Example 2) → ties everywhere; the equality branch matters
Two stones → keep the smaller one, then stop
Score is bounded by ~2x the total sum (< 10^9), so int suffices, but long in Java is safer
The monotone pointer must be reset per i and never moved backward

Code

from typing import List


class Solution:
    def stoneGameV(self, stoneValue: List[int]) -> int:
        """
        1563. Stone Game V
        Time: O(n^2)
        Space: O(n^2)
        """
        n = len(stoneValue)
        if n < 2:
            return 0

        # Prefix sums: sum(i..j) = P[j+1] - P[i]
        P = [0] * (n + 1)
        for i, x in enumerate(stoneValue):
            P[i + 1] = P[i] + x

        dp = [[0] * n for _ in range(n)]
        mL = [[0] * n for _ in range(n)]  # mL[i][k] = max_{k'<=k} (sum(i..k') + dp[i][k'])
        mR = [[0] * n for _ in range(n)]  # mR[k][j] = max_{k'>=k} (sum(k'..j) + dp[k'][j])

        for i in range(n - 1, -1, -1):
            mL[i][i] = stoneValue[i]
            mR[i][i] = stoneValue[i]
            p = i  # monotone split threshold for this i
            for j in range(i + 1, n):
                total = P[j + 1] - P[i]
                # smallest k in [i, j-1] with 2 * sum(i..k) >= total (else p == j)
                while p < j and 2 * (P[p + 1] - P[i]) < total:
                    p += 1

                # a tie at k == p lets Alice also keep the left side
                lb = p if (p <= j - 1 and 2 * (P[p + 1] - P[i]) == total) else p - 1

                best = 0
                if lb >= i:
                    best = mL[i][lb]
                if p + 1 <= j and mR[p + 1][j] > best:
                    best = mR[p + 1][j]
                dp[i][j] = best

                span = total + best  # sum(i..j) + dp[i][j]
                mL[i][j] = mL[i][j - 1] if mL[i][j - 1] > span else span
                mR[i][j] = mR[i + 1][j] if mR[i + 1][j] > span else span

        return dp[0][n - 1]

/**
 * 1563. Stone Game V
 * Time: O(n^2)
 * Space: O(n^2)
 */
class Solution {
    public int stoneGameV(int[] stoneValue) {
        int n = stoneValue.length;
        if (n < 2) {
            return 0;
        }

        // Prefix sums: sum(i..j) = P[j+1] - P[i]
        long[] P = new long[n + 1];
        for (int i = 0; i < n; i++) {
            P[i + 1] = P[i] + stoneValue[i];
        }

        int[][] dp = new int[n][n];
        int[][] mL = new int[n][n]; // mL[i][k] = max_{k'<=k} (sum(i..k') + dp[i][k'])
        int[][] mR = new int[n][n]; // mR[k][j] = max_{k'>=k} (sum(k'..j) + dp[k'][j])

        for (int i = n - 1; i >= 0; i--) {
            mL[i][i] = stoneValue[i];
            mR[i][i] = stoneValue[i];
            int p = i; // monotone split threshold for this i
            for (int j = i + 1; j < n; j++) {
                long total = P[j + 1] - P[i];
                // smallest k in [i, j-1] with 2 * sum(i..k) >= total (else p == j)
                while (p < j && 2 * (P[p + 1] - P[i]) < total) {
                    p++;
                }

                // a tie at k == p lets Alice also keep the left side
                int lb = (p <= j - 1 && 2 * (P[p + 1] - P[i]) == total) ? p : p - 1;

                int best = 0;
                if (lb >= i) {
                    best = mL[i][lb];
                }
                if (p + 1 <= j && mR[p + 1][j] > best) {
                    best = mR[p + 1][j];
                }
                dp[i][j] = best;

                int span = (int) (total + best); // sum(i..j) + dp[i][j]
                mL[i][j] = Math.max(mL[i][j - 1], span);
                mR[i][j] = Math.max(mR[i + 1][j], span);
            }
        }

        return dp[0][n - 1];
    }
}