#1690
Stone Game VII
specialist · 750 · lc medium +31 · verified · 58.7% accepted · 1,047 likes · top 55%
Description
Alice and Bob alternately remove the leftmost or rightmost stone from a row (Alice first). Each removal earns points equal to the sum of the remaining stones. Alice tries to maximize the score gap; Bob tries to minimize it. Return the difference in their scores when both play optimally.
Example 1:
Input: stones = [5,3,1,4,2]
Output: 6
Explanation:
- Alice removes 2 and gets 5 + 3 + 1 + 4 = 13 points. Alice = 13, Bob = 0, stones = [5,3,1,4].
- Bob removes 5 and gets 3 + 1 + 4 = 8 points. Alice = 13, Bob = 8, stones = [3,1,4].
- Alice removes 3 and gets 1 + 4 = 5 points. Alice = 18, Bob = 8, stones = [1,4].
- Bob removes 1 and gets 4 points. Alice = 18, Bob = 12, stones = [4].
- Alice removes 4 and gets 0 points. Alice = 18, Bob = 12, stones = [].
The score difference is 18 - 12 = 6.
Example 2:
Input: stones = [7,90,5,1,100,10,10,2]
Output: 122
Code
1
2
3