Watch 7 video solutions for Stone Game V, a hard level problem involving Array, Math, Dynamic Programming. This walkthrough by Fraz has 4,532 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 value of each row which is the sum of the values of all the stones in this row. Bob throws away the row which has the maximum value, and Alice's score increases by the value of the remaining row. If the value of the two rows are equal, 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.
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 row has the value 11 and the right row has value 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 16 (11 + 5). 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 18 (16 + 2). 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
Constraints:
1 <= stoneValue.length <= 5001 <= stoneValue[i] <= 106Problem Overview: You are given an array where each value represents stones in a pile. At every step you split the array into two non-empty parts. The player only keeps the side with the smaller sum (or either if equal) and gains that sum as score. The goal is to maximize the total score after repeatedly splitting until one element remains.
Approach 1: Dynamic Programming with Prefix Sums (O(n^3) time, O(n^2) space)
The straightforward strategy models the problem using dynamic programming. Define dp[i][j] as the maximum score obtainable from the subarray stoneValue[i..j]. For every interval, iterate over all possible split points k. Use a prefix sum array to compute leftSum and rightSum in O(1). If leftSum < rightSum, you must keep the left side and add leftSum + dp[i][k]. If leftSum > rightSum, keep the right side and add rightSum + dp[k+1][j]. When both sums are equal, take the maximum of both options. Because every interval tries all split points, the runtime becomes O(n^3) with O(n^2) memory for the DP table.
This approach relies heavily on fast subarray sum computation using prefix sums over the array. It is conceptually simple and mirrors the game rules directly, making it a reliable baseline solution.
Approach 2: Optimized Dynamic Programming with Recursive Memoization (O(n^2) time, O(n^2) space)
You can reduce redundant work by combining recursion with memoization and pruning unnecessary splits. Use a recursive function dfs(l, r) that returns the best score for the interval. Prefix sums again provide O(1) range sum queries. During the split iteration, observe that once the left sum exceeds the right sum (or vice versa), future splits only make the imbalance larger. This allows pruning or skipping portions of the search space.
Memoize results for each pair (l, r) so every subproblem is computed once. With careful pruning and reuse of intermediate values, the algorithm effectively processes about O(n^2) states and near O(n) transitions per interval on average, giving roughly O(n^2) practical complexity. This technique mixes dynamic programming with recursive state exploration common in game theory problems.
Recommended for interviews: Start by explaining the interval DP idea with prefix sums. That demonstrates understanding of subproblem structure and state transitions. Interviewers usually expect the DP formulation first. The optimized memoized approach shows deeper insight into pruning and state reuse, which is valuable when discussing performance improvements.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Dynamic Programming with Prefix Sums | O(n^3) | O(n^2) | Baseline solution that clearly models all splits. Good for understanding interval DP. |
| Optimized DP with Recursive Memoization | O(n^2) | O(n^2) | Preferred for larger inputs. Uses pruning and memoization to avoid redundant split evaluations. |