Loading problem…
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, they can **remove** either the leftmost stone or the rightmost stone from the row and receive points equal to the **sum of the remaining stones' values** in the row. The winner is the one with the higher score when there are no stones left to remove. Bob found that he will always lose this game (poor Bob, he always loses), so he decided to **minimize the score's difference**. Alice's goal is to **maximize the difference** in the score. Given an array of integers `stones` where `stones[i]` represents the value of the `i`th stone **from the left**, return *the **difference** in Alice and Bob's score if they both play **optimally***.
Example 1
Input: stones = [5,3,1,4,2]
Output: 6
Explanation: Alice removes 2 and scores 5 + 3 + 1 + 4 = 13. Bob removes 5 and scores 8. Alice removes 3 and scores 5. Bob removes 1 and scores 4. Alice removes 4 and scores 0. Alice has 18 and Bob has 12, a difference of 6.
Example 2
Input: stones = [7,90,5,1,100,10,10,2]
Output: 122
Explanation: Optimal removals from either end yield a final score difference of 122.
Example 3
Input: stones = [1,2]
Output: 2
Explanation: Alice removes the 1 (left), scoring the remaining stone 2; Bob then removes the last stone scoring 0. Difference 2 - 0 = 2.
dp[i][j] = the best score DIFFERENCE (mover minus opponent) on the sub-row stones[i..j]. Removing an end scores the sum of what stays and hands that smaller row to the opponent, whose lead subtracts. Prefix sums give the remaining sum in O(1); fill short rows first.
Run checks all cases above. Submit evaluates all test cases.