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.
This approach uses dynamic programming with prefix sums to efficiently calculate the score for partitions. The prefix sum allows quick calculation of any subarray sum, which is key to determining the optimal split at each step. By storing the maximum score possible starting at each index in a dp array, we can ensure that at each partition step, we choose the path that leads to the highest potential score.
The solution starts by computing the prefix sums for the input array, which helps in calculating subarray sums efficiently. Then, it uses a dynamic programming array, `dp`, where `dp[i]` represents the maximum score Alice can achieve starting from the `i`-th stone. The nested loops attempt each possible partitioning position `k` and compute scores of the left and right segments. Based on the comparison, it updates `dp` with the optimal choice. The time complexity of this approach is O(n^3) due to the nested loops for both partitioning positions and interval lengths.
Time Complexity: O(n^3)
Space Complexity: O(n)
This approach optimizes the dynamic programming strategy by incorporating recursive memoization. The recursive function breaks the stones into smaller subproblems and stores the computed results in a memoization table. This reduces redundant computations for overlapping subproblems.
This solution enhances the dynamic programming technique by utilizing a recursive function `dfs` which calculates the optimal score for a segment of stones from the `l`-th to the `r`-th. The results of these recursive calls are cached in a `memo`ization table to avoid recalculating scores for previously solved subproblems. The recursive decomposition reduces unnecessary O(n^3) evaluations.
Time Complexity: O(n^2)
Space Complexity: O(n^2)
First, we preprocess the prefix sum array s, where s[i] represents the sum of the first i elements of the array stoneValue.
Next, we design a function dfs(i, j), which represents the maximum score Alice can get from the stones in the subarray stoneValue within the index range [i, j]. The answer is dfs(0, n - 1).
The calculation process of the function dfs(i, j) is as follows:
i geq j, it means there is only one stone left, and Alice cannot split it, so return 0.k, i.e., i leq k < j, splitting the stones in the subarray stoneValue within the index range [i, j] into two parts: [i, k] and [k + 1, j]. We calculate a and b, which represent the total sum of the stones in the two parts, respectively. Then we calculate dfs(i, k) and dfs(k + 1, j), and update the answer.Note that if a < b and ans geq a times 2, this enumeration can be skipped; if a > b and ans geq b times 2, all subsequent enumerations can be skipped, and the loop can be exited directly.
Finally, we return the answer.
To avoid repeated calculations, we can use memoization and pruning to optimize the enumeration efficiency.
The time complexity is O(n^3), and the space complexity is O(n^2). Here, n is the length of the array stoneValue.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Dynamic Programming with Prefix Sums | Time Complexity: O(n^3) |
| Optimized Dynamic Programming with Recursive Memoization | Time Complexity: O(n^2) |
| Memoization + Pruning | — |
| 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. |
Leetcode 1563. Stone Game V • Fraz • 4,532 views views
Watch 6 more video solutions →Practice Stone Game V with our built-in code editor and test cases.
Practice on FleetCode