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, while the number of stones is **more than one**, they will do the following: 1. Choose an integer `x > 1`, and **remove** the leftmost `x` stones from the row. 2. Add the **sum** of the **removed** stones' values to the player's score. 3. 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: 5
Explanation: Alice removes the first 4 stones (score 2) and drops a stone of value 2; Bob is forced to take both remaining (score -3). Difference = 2 - (-3) = 5.
Example 2
Input: stones = [7,-6,5,10,5,-2,-6]
Output: 13
Explanation: Alice removes all stones at once for a score of 13; Bob gets nothing.
Example 3
Input: stones = [-10,-12]
Output: -22
Explanation: Only one move is possible: Alice must take both stones, scoring -22.
A move that removes the leftmost x stones and replaces them by their sum is exactly a choice of a prefix boundary — the merged left stone is always the running prefix sum. So each turn a player just picks an index i (i >= 1) and scores prefix[i]; the opponent then continues from i. Play the minimax over prefix boundaries right-to-left.
Run checks all cases above. Submit evaluates all test cases.