Loading 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 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: Round 1: split into [6,2,3] (11) and [4,5,5] (14). Bob throws away the larger right side, and Alice scores 11. Round 2: split [6,2,3] into [6] and [2,3] (5). Bob throws away [6], and Alice scores 5. Round 3: split [2,3] into [2] and [3], and Alice scores 2. Her total is 11 + 5 + 2 = 18.
Example 2
Input: stoneValue = [7,7,7,7,7,7,7]
Output: 28
Explanation: With all-equal stones Alice always gets to pick the side to keep, netting 28.
Example 3
Input: stoneValue = [4]
Output: 0
Explanation: A single stone can't be split, so no round is ever played and Alice scores 0.
dp[i][j] = the most Alice can score from the stones in [i..j]. She picks a split k; Bob discards the heavier half, Alice scores the lighter half's sum and recurses into it. Try every split, keep the max; solve short intervals before long ones.
Run checks all cases above. Submit evaluates all test cases.