Skip to main content

1563. Stone Game V

hard

Split a row of stones into two non-empty parts; the smaller-sum side is discarded and Alice's score grows by that sum. Interval DP over (start, end) with prefix-sum lookups.

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

Problem

There are several stones arranged in a row, and each stone has an associated value which is an integer given in the array stoneValue. In each round of the game, Alice divides the row into two non-empty rows (i.e. left row and right row), then Bob calculates the sum of values in each row, and throws away the row which has the maximum value of stones in it. Alice's score increases by the value of the remaining row. If the two rows have equal sum of values, then Bob lets Alice decide which row will be thrown away. The next round starts with the remaining row. The game ends when there is only one stone remaining. Alice's is initially zero. Return the maximum score that Alice can obtain.

Constraints

  • 1 <= stoneValue.length <= 500
  • 1 <= stoneValue[i] <= 10^6

Examples

Example 1

Input
stoneValue = [6,2,3,4,5,5]
Output
18

Explanation: In the first round, Alice divides the row to [6,2,3], [4,5,5]. The left sum is 11, and the right sum is 14. Bob throws away the right row and Alice's score is now 11. In the second round Alice divides the row to [6], [2,3]. This time Bob throws away the left row and Alice's score becomes 11 + 5 = 16. In the last round Alice has only one choice to divide the row which is [2], [3]. Bob throws away the right row and Alice's score is now 16 + 2 = 18. The game ends because only one stone is remaining in the row.

Example 2

Input
stoneValue = [7,7,7,7,7,7,7]
Output
28

Example 3

Input
stoneValue = [4]
Output
0

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

Interval DP. dp[i][j] = maximum score Alice can earn from stoneValue[i..j].

Hint 2

For each split point k in [i, j), compare leftSum = sum(i..k) and rightSum = sum(k+1..j).

Hint 3

If leftSum < rightSum: discard right, gain leftSum, recurse on dp[i][k]. If >: discard left, gain rightSum, recurse on dp[k+1][j]. If equal: Alice picks the better of the two.

Hint 4

Use prefix sums for O(1) interval sums. Fill by increasing interval length.

Solution approach

Reveal approach

Interval DP. Let dp[i][j] be the maximum score Alice can earn from stoneValue[i..j]. Precompute prefix sums for O(1) interval-sum lookups. For each interval (i, j) in increasing length, try every split index k in [i, j). Compute leftSum = sum(i, k) and rightSum = sum(k+1, j). If leftSum < rightSum, score = leftSum + dp[i][k]. If leftSum > rightSum, score = rightSum + dp[k+1][j]. If equal, Alice picks whichever recursion is larger, so score = max(leftSum + dp[i][k], rightSum + dp[k+1][j]). dp[i][j] = max over k of score. Return dp[0][n-1]. Base: dp[i][i] = 0 — a single stone yields no further score. Time: O(n^3).

Complexity

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

Related patterns

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

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 V 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 →