342. Stone Game III

Let dp[i] be the best score DIFFERENCE (mover minus opponent) reachable from stoneValue[i:]. Taking k = 1, 2, or 3 stones scores their running sum and hands the rest to the opponent, whose advantage subtracts. Scan right to left; the sign of dp[0] decides the winner.

One number per starting point

Rather than tracking two scores, track a single difference: dp[i] = the best value of (current player's score − opponent's score) achievable when the row stoneValue[i:] remains and it is the current player's move.

The recurrence

On stoneValue[i:] the player may take k = 1, 2, or 3 stones. Taking k scores their sum stoneValue[i] + ... + stoneValue[i+k-1], then the opponent plays from index i+k and guarantees dp[i+k] for themselves — which is -dp[i+k] from the mover's view:

dp[i] = max over k in {1,2,3} of ( sum(stoneValue[i..i+k-1]) - dp[i+k] )

Base: dp[n] = 0 (no stones, no difference). Scan i from n-1 down to 0.

Finally interpret dp[0] — the difference with Alice moving first:

• dp[0] > 0 → Alice wins,
• dp[0] < 0 → Bob wins,
• dp[0] == 0 → Tie.

Worked example

stoneValue = [1, 2, 3, 7], dp has size 5 with dp[4] = 0.

• i = 3: only k=1 → 7 - dp[4] = 7. dp[3] = 7.
• i = 2: k=1: 3 - dp[3] = 3-7 = -4; k=2: 3+7 - dp[4] = 10. dp[2] = 10.
• i = 1: k=1: 2 - dp[2] = -8; k=2: 2+3 - dp[3] = 5-7 = -2; k=3: 2+3+7 - dp[4] = 12. dp[1] = 12.
• i = 0: k=1: 1 - dp[1] = 1-12 = -11; k=2: 1+2 - dp[2] = 3-10 = -7; k=3: 1+2+3 - dp[3] = 6-7 = -1. dp[0] = -1.

dp[0] = -1 < 0, so Bob wins: no matter what Alice grabs from the front, Bob is left with a stronger remainder.

Complexity

• Time: O(n) — each of n states tries at most 3 moves.
• Space: O(n) for the dp array (compressible to O(1) with a 3-slot ring).

class Solution {
    public String stoneGameIII(int[] stoneValue) {
        int n = stoneValue.length;
        // dp[i] = best score difference (mover - opponent) reachable from stoneValue[i:].
        int[] dp = new int[n + 1];
        for (int i = n - 1; i >= 0; i--) {
            int take = 0;
            int best = Integer.MIN_VALUE;
            for (int k = 0; k < 3; k++) {
                if (i + k < n) {
                    take += stoneValue[i + k];
                    best = Math.max(best, take - dp[i + k + 1]);
                }
            }
            dp[i] = best;
        }
        if (dp[0] > 0) return "Alice";
        if (dp[0] < 0) return "Bob";
        return "Tie";
    }
}