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 ith 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.length2 <= n <= 10001 <= stones[i] <= 1000Problem 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.
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.
In this C implementation, we start by computing the prefix sums to get the sum of elements between any two indices quickly. We then fill a 2D DP table, where each cell dp[i][j] holds the maximum score difference the current player can secure from stones in the subarray stones[i...j]. The scores for each move are calculated using the prefix sums, and we use the results to populate the DP table iteratively.
Time Complexity: O(n^2)
Space Complexity: O(n^2)
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.
This C function uses recursion and memoization to track possible score differences by evaluating potential moves recursively. Recursive calls are cached with memoization to avoid recalculating results, reducing time spent on previously solved sub-problems.
Time Complexity: O(n^2) (with memoization)
Space Complexity: O(n^2)
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:
i > j, it means there are no stones currently, so return 0;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.
Python
Java
C++
Go
TypeScript
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.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Approach 1: Dynamic Programming with Pre-computed Prefix Sum | Time Complexity: |
| Approach 2: Recursive with Memoization | Time Complexity: |
| Memorization Search | — |
| Dynamic Programming | — |
| 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. |
Stone Game VII • Pepcoding • 4,354 views views
Watch 9 more video solutions →Practice Stone Game VII with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor