Compute the Optimal Prefix-Merging Game Difference

### Problem Alice and Bob alternate with Alice first. With more than one stone remaining, choose at least two leftmost stones, add their sum to the current player’s score, and replace that prefix by one leftmost stone of the same sum. Stop when only one stone remains. Alice maximizes and Bob minimizes Alice’s score minus Bob’s score. Return that difference under optimal play. ```cpp class Solution { public: int stoneGameVIII(vector<int>& stones); }; ``` ### Examples **Example 1:** ```text stones = [4,-1,-5] Output: 5 Explanation: Alice merges the first two for 3. Bob then scores -2 by merging the remaining stones, yielding 3-(-2)=5. Taking all initially yields only -2. ``` **Example 2:** ```text stones = [2,-4] Output: -2 Explanation: The only possible move scores -2 for Alice. ``` ### Constraints - `n == stones.length`, with `2 <= n <= 10^5`. - `-10^4 <= stones[i] <= 10^4`. ### Clarifying Questions Negative rewards are possible. The merged prefix remains available as one stone for subsequent turns; it is not discarded. ```hint Inspect the structure What remains after a prefix is merged, and whose objective applies on the next turn? ``` ### Reasoning checkpoints - Respect the evolving merged-prefix stone and every legal move under alternating optimal play. - Prove the score difference with negative rewards allowed, rather than maximizing one player's raw total. ### Optional extensions How would requiring exactly two stones per move change the recurrence?