#1563
Stone Game V
master · 1670 · lc hard +32 · verified · 41.6% accepted · 696 likes · top 22%
Description
Stones are arranged in a row, each with a value from the array stoneValue. Each round, Alice splits the row into two non-empty parts. Bob keeps the part with the smaller total and discards the larger one, and Alice's score increases by that kept sum. If both parts are equal, Alice picks which to keep. Play continues until one stone remains. Return the maximum score Alice can achieve, starting from zero.
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
Code
1
2
3