Stone Game V
There are several stones arranged in a row, and each stone has an associated value given by the integer array stoneValue.
In each round of the game:
- Alice divides the row into two non-empty rows, a left row and a right row.
- Bob calculates the value of each row, which is the sum of all stones in that row.
- Bob throws away the row with the maximum value, and Alice's score increases by the value of the remaining row.
- If the two rows have equal value, 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 score is initially zero.
Return the maximum score that Alice can obtain.
Example 1
Input
stoneValue = [6,2,3,4,5,5]Output
18Alice can first keep the left row worth 11, then keep [2,3] worth 5, then keep [2] worth 2, for a total score of 18.
Example 2
Input
stoneValue = [7,7,7,7,7,7,7]Output
28The maximum score Alice can obtain from these equal-valued stones is 28.
Constraints
- 1 <= stoneValue.length <= 500
- 1 <= stoneValue[i] <= 10^6