Stone Game VII — Medium Problem & Solution

Alice and Bob take turns removing a stone from either end of the row, Alice first. The player who removes a stone scores the sum of the remaining stones.

Difficulty: Medium
Topics: Arrays, Math, Dynamic Programming, Game Theory
Asked at: Amazon, Google, Microsoft
Time limit: 2 s
Memory limit: 256 MB
Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

Alice and Bob take turns removing a stone from either end of the row, Alice first. The player who removes a stone scores the sum of the remaining stones.

Alice plays to maximise the difference between her score and Bob's; Bob plays to minimise it. Return that difference with both playing optimally.

Example 1

Input: stones = [5,3,1,4,2]
Output: 6

Example 2

Input: stones = [7,90,5,1,100,10,10,2]
Output: 122

Example 3

Input: stones = [1,2]
Output: 2
Explanation: Alice removes the 1 and scores the remaining 2; Bob then scores 0.

Constraints

n == stones.length
2 <= n <= 1000
1 <= stones[i] <= 1000

How to solve Stone Game VII

Interval DP where dp[i][j] is the best score difference the player to move can force on stones[i..j]. Each move scores the sum of what remains and then flips the sign of the opponent's best result, so dp[i][j] = max(sum(i+1..j) - dp[i+1][j], sum(i..j-1) - dp[i][j-1]).

Approach

Build prefix sums so any window's total is O(1).
dp[i][i] = 0 — one stone left means the mover scores 0.
For increasing window lengths, take the better of dropping the left or the right stone.
Return dp[0][n-1].

Why it works

Tracking the difference rather than the two scores is what removes the player from the state: both play the same maximising rule, and subtracting the opponent's best difference flips the perspective automatically. That halves the state space and is the standard shape for symmetric two-player games.

Complexity

Time — O(n²)
Space — O(n²)

Pitfalls

The mover scores what remains, not the stone removed.
dp[i][i] = 0, not stones[i] — removing the last stone leaves nothing to score.
Subtract the opponent's result; adding it would model cooperation, not competition.

Reference solution

Python

from typing import List

def stoneGameVII(stones: List[int]) -> int:
    n = len(stones)
    pre = [0] * (n + 1)
    for i in range(n):
        pre[i + 1] = pre[i] + stones[i]
    dp = [[0] * n for _ in range(n)]
    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            dp[i][j] = max(pre[j + 1] - pre[i + 1] - dp[i + 1][j],
                           pre[j] - pre[i] - dp[i][j - 1])
    return dp[0][n - 1]

JavaScript

var stoneGameVII = function(stones) {
    var n = stones.length, i, j;
    var pre = [0];
    for (i = 0; i < n; i++) pre.push(pre[i] + stones[i]);
    var dp = [];
    for (i = 0; i < n; i++) {
        var row = [];
        for (j = 0; j < n; j++) row.push(0);
        dp.push(row);
    }
    for (var len = 2; len <= n; len++) {
        for (i = 0; i + len - 1 < n; i++) {
            j = i + len - 1;
            var a = pre[j + 1] - pre[i + 1] - dp[i + 1][j];
            var b = pre[j] - pre[i] - dp[i][j - 1];
            dp[i][j] = a > b ? a : b;
        }
    }
    return dp[0][n - 1];
};

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

All 667 arrays problems · the whole catalogue