Stone Game VIII
Alice and Bob take turns playing a game, with Alice starting first.
There are n stones arranged in a row. On each player's turn, while the number of stones is more than one, they will do the following:
- Choose an integer
x > 1, and remove the leftmostxstones from the row. - Add the sum of the removed stones' values to the player's score.
- Place a new stone, whose value is equal to that sum, on the left side of the row.
The game stops when only one stone is left in the row.
The score difference between Alice and Bob is (Alice's score - Bob's score). Alice's goal is to maximize the score difference, and Bob's goal is to minimize the score difference.
Given an integer array stones of length n where stones[i] represents the value of the i^th stone from the left, return the score difference between Alice and Bob if they both play optimally.
Example 1
Input
stones = [-1,2,-3,4,-5]Output
5Alice can remove the first 4 stones for a score of 2, then Bob removes the remaining 2 stones for a score of -3, so the difference is 2 - (-3) = 5.
Example 2
Input
stones = [7,-6,5,10,5,-2,-6]Output
13Alice removes all stones for a score of 13, leaving Bob with 0, so the score difference is 13.
Constraints
- n == stones.length
- 2 <= n <= 10^5
- -10^4 <= stones[i] <= 10^4