Stone Game V
There are several stones arranged in a row, and each stone has an associated value given in the array stoneValue[i].
In each round, Alice divides the row into two non-empty parts (left and right), then Bob discards one part and Alice keeps the other. The round ends and the score for that round is the sum of values of the stones Alice keeps. Then the remaining part is played again.
The game ends when only one stone remains. Alice's total score is the sum of scores from all rounds. Assuming both play optimally, return the maximum score Alice can achieve.
Examples
Input: [6,2,3,4,5,5]
Output: 18
Input: [7,7,7,7]
Output: 28
Hints
Use interval DP. Define `dp[l][r]` as max score Alice can get from subarray `stoneValue[l..r]`.
For each split point `m` between `l` and `r`, Alice divides into `[l..m]` and `[m+1..r]`. Bob discards the side with smaller sum. If left < right, Alice gets left sum + dp[l][m]. If right < left, Alice gets right sum + dp[m+1][r].
If left sum == right sum, Alice can choose the better continuation. Base case: `dp[i][i] = 0`. Use prefix sums for O(1) range sum queries.
Related Problems
Stone Game V
There are several stones arranged in a row, and each stone has an associated value given in the array `stoneValue[i]`.