MediumArrayMathDynamic ProgrammingGame Theory

Stone Game VII

1 approach, code in every language

Alice and Bob play a game with a row of stones, where the value of each stone is given in the array stones. Alice goes first and the players alternate turns. On a turn, a player removes either the leftmost or the rightmost remaining stone and earns points equal to the sum of the values of all stones that are still on the row after the removal.

Both players play optimally, and each one wants to maximize the difference between their own total score and the opponent's total score. Return the difference between Alice's score and Bob's score at the end of the game assuming both play optimally.

Example 1

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

Output: 6

With optimal play the players trim the row from both ends so that Alice keeps a lead of exactly 6 points over Bob by always choosing the end that maximizes her own margin.

Example 2

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

Output: 122

Each removal scores the sum of what remains, so early moves are worth the most. Optimal alternating choices leave Alice ahead by 122 points.

Constraints

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

Interval DP with Prefix Sums

Use prefix sums to score removals in O(1) and a range DP that returns the optimal score margin for every subarray.

Loading animation…

Intuition

When a player faces the subarray from index i to index j, the score they gain from a move is the sum of whatever remains, so precomputing prefix sums lets us get any range total instantly. Define dp[i][j] as the best achievable score margin (current player minus opponent) when only stones i..j are left. If the current player removes stones[i], they immediately earn the sum of i+1..j and then the opponent plays optimally on that smaller range, contributing negatively as dp[i+1][j]. Removing stones[j] symmetrically earns the sum of i..j-1 minus dp[i][j-1]. The player picks whichever option yields the larger margin, so dp[i][j] is the maximum of those two choices. Building this table from the shortest ranges upward gives dp[0][n-1], the margin under optimal play by both sides.

Algorithm walkthrough

1Build a prefix-sum array so the total of any range i..j is prefix[j + 1] - prefix[i] in constant time.
2Initialize dp[i][i] = 0 because a single remaining stone forces a removal that leaves nothing to score.
3Iterate over increasing range lengths so that smaller subranges are solved before larger ones.
4For a range i..j, compute removing the left stone: (sum of i+1..j) - dp[i+1][j].
5Compute removing the right stone: (sum of i..j-1) - dp[i][j-1], then set dp[i][j] to the larger of the two.
6Return dp[0][n-1], the optimal score difference for the full row.

Implementation

class Solution:
    def stoneGameVII(self, stones: List[int]) -> int:
        n = len(stones)
        prefix = [0] * (n + 1)
        for i in range(n):
            prefix[i + 1] = prefix[i] + stones[i]

        dp = [[0] * n for _ in range(n)]
        for length in range(2, n + 1):
            for i in range(0, n - length + 1):
                j = i + length - 1
                take_left = (prefix[j + 1] - prefix[i + 1]) - dp[i + 1][j]
                take_right = (prefix[j] - prefix[i]) - dp[i][j - 1]
                dp[i][j] = max(take_left, take_right)
        return dp[0][n - 1]

Time

O(n^2)

Space

O(n^2)

There are O(n^2) subranges and each is resolved in O(1) thanks to prefix sums; space can be reduced to O(n) with a rolling diagonal if needed.

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Dynamic Programming

After the pattern

Now solve one you haven't seen.

Reading a pattern isn't the same as using it. The practice set has 1,194 original problems on the same techniques, each graded in your browser.

Open the practice set Start the FDE path

1,194 problems · 15,062 graded tests · free