1690. Stone Game VII Solution & Explanation

The problem

Alice and Bob take turns playing a game, with Alice starting first.

There are n stones arranged in a row. On each player's turn, they can remove either the leftmost stone or the rightmost stone from the row and receive points equal to the sum of the remaining stones' values in the row. The winner is the one with the higher score when there are no stones left to remove.

Bob found that he will always lose this game (poor Bob, he always loses), so he decided to minimize the score's difference. Alice's goal is to maximize the difference in the score.

Given an array of integers stones where stones[i] represents the value of the i^th stone from the left, return the difference in Alice and Bob's score if they both play optimally.

Example 1:

Input: stones = [5,3,1,4,2]
Output: 6
Explanation: 
- Alice removes 2 and gets 5 + 3 + 1 + 4 = 13 points. Alice = 13, Bob = 0, stones = [5,3,1,4].
- Bob removes 5 and gets 3 + 1 + 4 = 8 points. Alice = 13, Bob = 8, stones = [3,1,4].
- Alice removes 3 and gets 1 + 4 = 5 points. Alice = 18, Bob = 8, stones = [1,4].
- Bob removes 1 and gets 4 points. Alice = 18, Bob = 12, stones = [4].
- Alice removes 4 and gets 0 points. Alice = 18, Bob = 12, stones = [].
The score difference is 18 - 12 = 6.

Example 2:

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

Constraints:

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

Approach overview

Problem Overview: You are given an array where each value represents a stone. Two players remove a stone from either end of the row. Instead of gaining the removed stone's value, the player gains the sum of the remaining stones. Both players play optimally, and the goal is to compute the maximum difference in score between Alice and Bob.

Approach 1: Dynamic Programming with Pre-computed Prefix Sum (O(n²) time, O(n²) space)

This approach models the game as a classic interval dynamic programming problem. Define dp[i][j] as the maximum score difference the current player can achieve from the subarray stones[i..j]. When a player removes the left stone, the gained score equals the sum of the remaining stones (i+1..j). If the right stone is removed, the gained score equals the sum of (i..j-1). Use a prefix sum array so range sums are computed in O(1). The recurrence becomes dp[i][j] = max(sum(i+1..j) - dp[i+1][j], sum(i..j-1) - dp[i][j-1]). Iterate over subarray lengths from small to large so smaller states are solved first. This produces the optimal score difference for the full interval dp[0][n-1]. The algorithm runs in O(n²) time because every pair (i, j) is evaluated once.

Approach 2: Recursive with Memoization (O(n²) time, O(n²) space)

The same recurrence can be expressed using recursion with memoization. Define a recursive function solve(i, j) representing the best score difference achievable from the interval [i, j]. At each step, simulate removing the left or right stone, compute the resulting score using prefix sums, and subtract the opponent's optimal response returned by the recursive call. Memoize results in a 2D cache so each state is computed once. Without memoization the recursion explores exponential game paths, but caching reduces it to O(n²). This approach mirrors the logic of optimal play in game theory problems and is often easier to reason about before converting to bottom‑up DP.

Recommended for interviews: The bottom‑up DP with prefix sums is the expected solution. It shows you recognize the interval DP pattern and can optimize repeated sum calculations. Starting with the recursive memoized version helps demonstrate understanding of optimal substructure and competitive decision making before translating it into an iterative DP table over the array.

Approach 1: Approach 1: Dynamic Programming with Pre-computed Prefix Sum

This approach uses dynamic programming along with pre-computed prefix sums to efficiently calculate the score differences.

We maintain a 2D DP table where dp[i][j] represents the maximum score difference the current player can achieve over the other player from index i to j. The prefix sums help in computing the sum of the stones between any two indices in constant time, which we require to decide which stone to remove to maximize the score difference.

Python

class Solution:
    def stoneGameVII(self, stones: List[int]) -> int:
        n = len(stones)
        prefix_sum = [0] * (n + 1)
        for i in range(n):
            prefix_sum[i + 1] = prefix_sum[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
                score_remove_left = prefix_sum[j + 1] - prefix_sum[i + 1]
                score_remove_right = prefix_sum[j] - prefix_sum[i]
                dp[i][j] = max(score_remove_left - dp[i + 1][j], score_remove_right - dp[i][j - 1])

        return dp[0][n - 1]

Java

import java.util.Arrays;

class Solution {
    public int stoneGameVII(int[] stones) {
        int n = stones.length;
        int[] prefixSum = new int[n + 1];
        for (int i = 0; i < n; i++)
            prefixSum[i + 1] = prefixSum[i] + stones[i];
        int[][] dp = new int[n][n];

        for (int length = 2; length <= n; length++) {
            for (int i = 0; i <= n - length; i++) {
                int j = i + length - 1;
                int scoreRemoveLeft = prefixSum[j + 1] - prefixSum[i + 1];
                int scoreRemoveRight = prefixSum[j] - prefixSum[i];
                dp[i][j] = Math.max(scoreRemoveLeft - dp[i + 1][j], scoreRemoveRight - dp[i][j - 1]);
            }
        }
        return dp[0][n - 1];
    }
}

C++

#include <vector>
#include <numeric>
#include <algorithm>

class Solution {
public:
    int stoneGameVII(std::vector<int>& stones) {
        int n = stones.size();
        std::vector<int> prefixSum(n + 1, 0);
        for (int i = 0; i < n; ++i) prefixSum[i + 1] = prefixSum[i] + stones[i];
        std::vector<std::vector<int>> dp(n, std::vector<int>(n, 0));

        for (int length = 2; length <= n; ++length) {
            for (int i = 0; i <= n - length; ++i) {
                int j = i + length - 1;
                int scoreRemoveLeft = prefixSum[j + 1] - prefixSum[i + 1];
                int scoreRemoveRight = prefixSum[j] - prefixSum[i];
                dp[i][j] = std::max(scoreRemoveLeft - dp[i + 1][j], scoreRemoveRight - dp[i][j - 1]);
            }
        }
        return dp[0][n - 1];
    }
};

JavaScript

var stoneGameVII = function(stones) {
    const n = stones.length;
    const prefixSum = Array(n + 1).fill(0);
    for (let i = 0; i < n; i++)
        prefixSum[i + 1] = prefixSum[i] + stones[i];
    const dp = Array.from({ length: n }, () => Array(n).fill(0));

    for (let length = 2; length <= n; length++) {
        for (let i = 0; i <= n - length; i++) {
            const j = i + length - 1;
            const scoreRemoveLeft = prefixSum[j + 1] - prefixSum[i + 1];
            const scoreRemoveRight = prefixSum[j] - prefixSum[i];
            dp[i][j] = Math.max(scoreRemoveLeft - dp[i + 1][j], scoreRemoveRight - dp[i][j - 1]);
        }
    }
    return dp[0][n - 1];
};

#include <stdio.h>
#include <string.h>

int stoneGameVII(int* stones, int stonesSize) {
    int prefixSum[stonesSize + 1];
    prefixSum[0] = 0;
    for (int i = 0; i < stonesSize; i++)
        prefixSum[i + 1] = prefixSum[i] + stones[i];

    int dp[stonesSize][stonesSize];
    memset(dp, 0, sizeof(dp));

    for (int length = 2; length <= stonesSize; length++) {
        for (int i = 0; i <= stonesSize - length; i++) {
            int j = i + length - 1;
            int scoreRemoveLeft = prefixSum[j + 1] - prefixSum[i + 1];
            int scoreRemoveRight = prefixSum[j] - prefixSum[i];
            dp[i][j] = fmax(scoreRemoveLeft - dp[i + 1][j], scoreRemoveRight - dp[i][j - 1]);
        }
    }
    return dp[0][stonesSize - 1];
}

using System;

public class Solution {
    public int StoneGameVII(int[] stones) {
        int n = stones.Length;
        int[] prefixSum = new int[n + 1];
        for (int i = 0; i < n; i++)
            prefixSum[i + 1] = prefixSum[i] + stones[i];
        int[,] dp = new int[n, n];

        for (int length = 2; length <= n; length++) {
            for (int i = 0; i <= n - length; i++) {
                int j = i + length - 1;
                int scoreRemoveLeft = prefixSum[j + 1] - prefixSum[i + 1];
                int scoreRemoveRight = prefixSum[j] - prefixSum[i];
                dp[i, j] = Math.Max(scoreRemoveLeft - dp[i+1, j], scoreRemoveRight - dp[i, j-1]);
            }
        }
        return dp[0, n - 1];
    }
}

The Python implementation uses lists to store prefix sums and the DP table. This allows the calculation of maximum score differences in each player’s favor using pre-stored sums for any subarray, leading to an efficient solution.

Complexity

Time Complexity: O(n^2)
Space Complexity: O(n^2)

Try this approach in the editor

Approach 2: Approach 2: Recursive with Memoization

This approach leverages recursive backtracking with memoization to explore all possible game states and store previously computed results to prevent redundant calculations. Unlike the iterative DP approach, this recursive strategy keeps track of outcomes by diving directly into decision trees, thus exposing base-level game decisions before accumulating overall results with stored solutions.

Python

class Solution:
    def stoneGameVII(self, stones: List[int]) -> int:
        def dfs(left, right, sum_):
            if left == right:
                return 0
            if (left, right) in memo:
                return memo[(left, right)]
            removeLeft = sum_ - stones[left] - dfs(left + 1, right, sum_ - stones[left])
            removeRight = sum_ - stones[right] - dfs(left, right - 1, sum_ - stones[right])
            memo[(left, right)] = max(removeLeft, removeRight)
            return memo[(left, right)]

        total = sum(stones)
        memo = {}
        return dfs(0, len(stones) - 1, total)

Java

import java.util.Arrays;

class Solution {
    public int dfs(int[] stones, int left, int right, int sum, int[][] memo) {
        if (left == right) return 0;
        if (memo[left][right] != -1) return memo[left][right];
        int removeLeft = sum - stones[left] - dfs(stones, left + 1, right, sum - stones[left], memo);
        int removeRight = sum - stones[right] - dfs(stones, left, right - 1, sum - stones[right], memo);
        return memo[left][right] = Math.max(removeLeft, removeRight);
    }

    public int stoneGameVII(int[] stones) {
        int sum = Arrays.stream(stones).sum();
        int[][] memo = new int[stones.length][stones.length];
        for (int[] row : memo) Arrays.fill(row, -1);
        return dfs(stones, 0, stones.length - 1, sum, memo);
    }
}

C++

#include <vector>
#include <numeric>
#include <string.h>

using namespace std;

class Solution {
public:
    int dfs(vector<int>& stones, int left, int right, int sum, vector<vector<int>>& memo) {
        if (left == right) return 0;
        if (memo[left][right] != -1) return memo[left][right];
        int removeLeft = sum - stones[left] - dfs(stones, left + 1, right, sum - stones[left], memo);
        int removeRight = sum - stones[right] - dfs(stones, left, right - 1, sum - stones[right], memo);
        return memo[left][right] = max(removeLeft, removeRight);
    }

    int stoneGameVII(vector<int>& stones) {
        int sum = accumulate(stones.begin(), stones.end(), 0);
        vector<vector<int>> memo(stones.size(), vector<int>(stones.size(), -1));
        return dfs(stones, 0, stones.size() - 1, sum, memo);
    }
};

JavaScript

var stoneGameVII = function(stones) {
    const n = stones.length;
    const memo = Array.from({ length: n }, () => Array(n).fill(-1));

    const dfs = (left, right, sum) => {
        if (left === right) return 0;
        if (memo[left][right] !== -1) return memo[left][right];
        const removeLeft = sum - stones[left] - dfs(left + 1, right, sum - stones[left]);
        const removeRight = sum - stones[right] - dfs(left, right - 1, sum - stones[right]);
        return memo[left][right] = Math.max(removeLeft, removeRight);
    };

    const total = stones.reduce((a, b) => a + b, 0);
    return dfs(0, n - 1, total);
};

#include <stdio.h>
#include <string.h>

int max(int a, int b) {
    return (a > b) ? a : b;
}

int dfs(int* stones, int left, int right, int sum, int** memo) {
    if (left == right) return 0;
    if (memo[left][right] != -1) return memo[left][right];
    int removeLeft = sum - stones[left] - dfs(stones, left + 1, right, sum - stones[left], memo);
    int removeRight = sum - stones[right] - dfs(stones, left, right - 1, sum - stones[right], memo);
    memo[left][right] = max(removeLeft, removeRight);
    return memo[left][right];
}

int stoneGameVII(int* stones, int stonesSize) {
    int sum = 0;
    for (int i = 0; i < stonesSize; i++)
        sum += stones[i];
    int** memo = (int**) malloc(stonesSize * sizeof(int*));
    for (int i = 0; i < stonesSize; i++)
        memo[i] = (int*) malloc(stonesSize * sizeof(int));
    for (int i = 0; i < stonesSize; i++)
        for (int j = 0; j < stonesSize; j++)
            memo[i][j] = -1;
    return dfs(stones, 0, stonesSize - 1, sum, memo);
}

using System;
using System.Collections.Generic;

public class Solution {
    private int dfs(int[] stones, int left, int right, int sum, int[,] memo) {
        if (left == right) return 0;
        if (memo[left, right] != -1) return memo[left, right];
        int removeLeft = sum - stones[left] - dfs(stones, left + 1, right, sum - stones[left], memo);
        int removeRight = sum - stones[right] - dfs(stones, left, right - 1, sum - stones[right], memo);
        memo[left, right] = Math.Max(removeLeft, removeRight);
        return memo[left, right];
    }

    public int StoneGameVII(int[] stones) {
        int sum = 0;
        foreach (var stone in stones) sum += stone;
        int[,] memo = new int[stones.Length, stones.Length];
        for (int i = 0; i < stones.Length; i++)
            for (int j = 0; j < stones.Length; j++)
                memo[i, j] = -1;
        return dfs(stones, 0, stones.Length - 1, sum, memo);
    }
}

The Python solution uses recursive depth-first search combined with a dictionary for memoization to optimize state explorations. Each game state leads to further recursion unless already encountered, in which case stored results are used, thereby shortening decision times.

Complexity

Time Complexity: O(n^2) with memoization
Space Complexity: O(n^2)

Try this approach in the editor

Approach 3: Memorization Search

First, we preprocess to get the prefix sum array s, where s[i] represents the total sum of the first i stones.

Next, we design a function dfs(i, j), which represents the score difference between the first and second players when the remaining stones are stones[i], stones[i + 1], \dots, stones[j]. The answer is dfs(0, n - 1).

The calculation process of the function dfs(i, j) is as follows:

If i > j, it means there are no stones currently, so return 0;
Otherwise, the first player has two choices, which are to remove stones[i] or stones[j], and then calculate the score difference, i.e., a = s[j + 1] - s[i + 1] - dfs(i + 1, j) and b = s[j] - s[i] - dfs(i, j - 1). We take the larger of the two as the return value of dfs(i, j).

During the process, we use memorization search, i.e., use an array f to record the return value of the function dfs(i, j), to avoid repeated calculations.

The time complexity is O(n^2), and the space complexity is O(n^2). Here, n is the number of stones.

TypeScript

function stoneGameVII(stones: number[]): number {
    const n = stones.length;
    const s: number[] = Array(n + 1).fill(0);
    for (let i = 0; i < n; ++i) {
        s[i + 1] = s[i] + stones[i];
    }
    const f: number[][] = Array.from({ length: n }, () => Array(n).fill(0));
    const dfs = (i: number, j: number): number => {
        if (i > j) {
            return 0;
        }
        if (f[i][j]) {
            return f[i][j];
        }
        const a = s[j + 1] - s[i + 1] - dfs(i + 1, j);
        const b = s[j] - s[i] - dfs(i, j - 1);
        return (f[i][j] = Math.max(a, b));
    };
    return dfs(0, n - 1);
}

func stoneGameVII(stones []int) int {
	n := len(stones)
	s := make([]int, n+1)
	f := make([][]int, n)
	for i, x := range stones {
		s[i+1] = s[i] + x
		f[i] = make([]int, n)
	}
	var dfs func(int, int) int
	dfs = func(i, j int) int {
		if i > j {
			return 0
		}
		if f[i][j] != 0 {
			return f[i][j]
		}
		a := s[j+1] - s[i+1] - dfs(i+1, j)
		b := s[j] - s[i] - dfs(i, j-1)
		f[i][j] = max(a, b)
		return f[i][j]
	}
	return dfs(0, n-1)
}

Try this approach in the editor

Approach 4: Dynamic Programming

We can convert the memoization search in Solution 1 into dynamic programming. We define f[i][j] as the score difference between the first and second players when the remaining stones are stones[i], stones[i + 1], \dots, stones[j]. Therefore, the answer is f[0][n - 1].

The state transition equation is as follows:

$f[i][j] = max(s[j + 1] - s[i + 1] - f[i + 1][j], s[j] - s[i] - f[i][j - 1])

When calculating f[i][j], we need to ensure that f[i + 1][j] and f[i][j - 1] have been calculated. Therefore, we need to enumerate i in descending order and j in ascending order.

Finally, the answer is f[0][n - 1].

The time complexity is O(n^2), and the space complexity is O(n^2). Here, n$ is the number of stones.

TypeScript

function stoneGameVII(stones: number[]): number {
    const n = stones.length;
    const s: number[] = Array(n + 1).fill(0);
    for (let i = 0; i < n; ++i) {
        s[i + 1] = s[i] + stones[i];
    }
    const f: number[][] = Array.from({ length: n }, () => Array(n).fill(0));
    for (let i = n - 2; ~i; --i) {
        for (let j = i + 1; j < n; ++j) {
            f[i][j] = Math.max(s[j + 1] - s[i + 1] - f[i + 1][j], s[j] - s[i] - f[i][j - 1]);
        }
    }
    return f[0][n - 1];
}

func stoneGameVII(stones []int) int {
	n := len(stones)
	s := make([]int, n+1)
	for i, x := range stones {
		s[i+1] = s[i] + x
	}
	f := make([][]int, n)
	for i := range f {
		f[i] = make([]int, n)
	}
	for i := n - 2; i >= 0; i-- {
		for j := i + 1; j < n; j++ {
			f[i][j] = max(s[j+1]-s[i+1]-f[i+1][j], s[j]-s[i]-f[i][j-1])
		}
	}
	return f[0][n-1]
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Approach 1: Dynamic Programming with Pre-computed Prefix Sum	Time Complexity: `O(n^2)` Space Complexity: `O(n^2)`
Approach 2: Recursive with Memoization	Time Complexity: `O(n^2)` with memoization Space Complexity: `O(n^2)`
Memorization Search	–
Dynamic Programming	–

Complexity analysis

Approach	Time	Space	When to Use
Dynamic Programming with Prefix Sum	O(n²)	O(n²)	Best general solution. Efficient for constraints up to several thousand elements.
Recursive with Memoization	O(n²)	O(n²)	Useful for understanding the game strategy and deriving the DP recurrence.

Frequently asked questions

Is Stone Game VII easy or hard?

Stone Game VII is rated Medium on LeetCode but requires recognizing the interval dynamic programming pattern. The difficulty comes from modeling the score difference and handling optimal decisions from both players.

Stone Game VII Python/Java solution

In Python or Java, implement a prefix sum array and a 2D DP table. Iterate over subarray lengths and compute dp[i][j] using the recurrence max(sum(i+1..j) - dp[i+1][j], sum(i..j-1) - dp[i][j-1]). This yields the final score difference at dp[0][n-1].

How to solve Stone Game VII in O(n)?

An O(n) solution is not known for this problem because the state depends on every possible subarray interval. The optimal approach evaluates all pairs (i, j) using dynamic programming, resulting in O(n^2) time complexity.

What is the best approach for Stone Game VII?

Dynamic Programming with prefix sums is the standard solution. Define dp[i][j] as the maximum score difference achievable from the subarray stones[i..j]. Each move removes a stone from either end and adds the remaining sum, which can be computed in O(1) using prefix sums. The DP evaluates all intervals in O(n^2) time.

Is Stone Game VII asked at Google/Amazon/Meta?

Game theory and interval dynamic programming problems like Stone Game VII frequently appear in interviews at large tech companies including Amazon, Google, and Meta. Interviewers use them to test reasoning about optimal play, recursion, and DP state transitions.

What data structure is used in Stone Game VII?

The core data structures are arrays and a 2D DP table. A prefix sum array is used to compute subarray sums in constant time, while dp[i][j] stores the optimal score difference for each interval.

What is the time complexity of Stone Game VII?

The optimal dynamic programming solution runs in O(n^2) time and uses O(n^2) space. There are O(n^2) subarray states (i, j), and each state performs constant-time calculations using precomputed prefix sums.

Stone Game VII solution and explanation

The problem

Approach overview

Approach 1: Approach 1: Dynamic Programming with Pre-computed Prefix Sum

Approach 2: Approach 2: Recursive with Memoization

Approach 3: Memorization Search

Approach 4: Dynamic Programming

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Stone Game VII solution and explanation

The problem

Approach overview

Approach 1: Approach 1: Dynamic Programming with Pre-computed Prefix Sum

Approach 2: Approach 2: Recursive with Memoization

Approach 3: Memorization Search

Approach 4: Dynamic Programming

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems