Skip to main content

1690. Stone Game VII

medium

Players alternate removing the leftmost or rightmost stone; the mover scores the sum of the remaining stones. Interval DP on score difference — same shape as classic Stone Game with prefix sums.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

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 ith stone from the left, return the difference in Alice and Bob's score if they both play optimally.

Constraints

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

Examples

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]. The score difference is 18 - 12 = 6.

Example 2

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

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

dp[i][j] = max score difference the current player can achieve on stones[i..j].

Hint 2

If the mover removes stones[i], they gain sum(stones[i+1..j]) - dp[i+1][j]. If they remove stones[j], they gain sum(stones[i..j-1]) - dp[i][j-1].

Hint 3

Use prefix sums for O(1) range-sum lookups.

Hint 4

Base: dp[i][i] = 0 — a single remaining stone is removed for 0 points (the remaining sum is empty).

Solution approach

Reveal approach

Interval DP on score difference, mirroring Stone Game (877). dp[i][j] is the maximum score difference (current player minus opponent) achievable on stones[i..j]. Build a prefix-sum array so sum(i, j) = prefix[j+1] - prefix[i] is O(1). For each interval length from 2 to n and each (i, j): two choices — remove the left stone for a current gain of sum(i+1, j) and switch perspective, dp[i+1][j] flipped sign; or remove the right stone for gain sum(i, j-1) - dp[i][j-1]. So dp[i][j] = max(sum(i+1, j) - dp[i+1][j], sum(i, j-1) - dp[i][j-1]). Base: dp[i][i] = 0. Return dp[0][n-1].

Complexity

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

Related patterns

  • dynamic-programming
  • interval-dp
  • game-theory
  • prefix-sum

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Google

Practice these live with InterviewChamp.AI

Drill Stone Game VII and 2D Dynamic Programming problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →