Stone Game VII
Alice and Bob take turns removing stones from a row, with Alice going first.
In each turn, a player removes either the first or the last stone from the row. The player then receives points equal to the sum of the remaining stones in the row (after removal). The game ends when no stones remain.
Assuming both play optimally, return the maximum score difference (Alice's score minus Bob's score) that Alice can achieve.
Examples
Input: [5,3,1,4,2]
Output: 6
Input: [7,8,8,10,4]
Output: 13
Hints
Use interval DP. Define `dp[l][r]` as the maximum score difference the current player can achieve from subarray `stones[l..r]`.
If the current player takes the left stone, they get `sum(l+1..r) - dp[l+1][r]`. If they take the right stone, they get `sum(l..r-1) - dp[l][r-1]`. Take the max of these two.
Precompute prefix sums for O(1) range sum queries. Base case: when `l == r`, the player takes the only stone and gets 0 (since no stones remain).
Related Problems
Stone Game VII
Alice and Bob take turns removing stones from a row, with Alice going first.