Stone Game VII

Medium
1049.

Stone Game VII

Stone Game VII is a medium coding problem on arrays, dynamic programming and math, asked in Amazon, Google and Microsoft interviews.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} stones
 * @return {number}
 */
var stoneGameVII = function(stones) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Stone Game VII — Solution in Python, Java & C++

Stone Game VII solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Stone Game VII is a medium coding problem on arrays, dynamic programming and math, asked in Amazon, Google and Microsoft interviews.

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

Hints for Stone Game VII

  1. Hint 1

    The state is the remaining window stones[i..j] — whose turn it is does not need to be stored.

  2. Hint 2

    Let dp[i][j] be the best difference the player to move can force on that window.

  3. Hint 3

    Removing the left stone scores sum(i+1..j) and hands the opponent dp[i+1][j], so the net is sum - dp[i+1][j].

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

  1. Build prefix sums so any window's total is O(1).
  2. dp[i][i] = 0 — one stone left means the mover scores 0.
  3. For increasing window lengths, take the better of dropping the left or the right stone.
  4. 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]

Java

public static int stoneGameVII(int[] stones) {
    int n = stones.length;
    int[] pre = new int[n + 1];
    for (int i = 0; i < n; i++) pre[i + 1] = pre[i] + stones[i];
    int[][] dp = new int[n][n];
    for (int len = 2; len <= n; len++) {
        for (int i = 0; i + len - 1 < n; i++) {
            int j = i + len - 1;
            dp[i][j] = Math.max(pre[j + 1] - pre[i + 1] - dp[i + 1][j],
                                pre[j] - pre[i] - dp[i][j - 1]);
        }
    }
    return dp[0][n - 1];
}

C++

int stoneGameVII(vector<int>& stones) {
    int n = (int) stones.size();
    vector<int> pre(n + 1, 0);
    for (int i = 0; i < n; i++) pre[i + 1] = pre[i] + stones[i];
    vector<vector<int>> dp(n, vector<int>(n, 0));
    for (int len = 2; len <= n; len++) {
        for (int i = 0; i + len - 1 < n; i++) {
            int j = i + len - 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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Dynamic Programming