Stone Game VIII
Alice and Bob take turns removing stones from a row, with Alice going first.
During a player's turn, they must remove at least 2 piles from the left end. The player receives points equal to the sum of all removed piles.
The twist: Each turn, a player chooses to either:
- Take exactly 2 piles from the left, or
- Take the same number of piles as the opponent took on the previous turn (must be at least 2).
Alice's first move must be taking exactly 2 piles. Assuming both play optimally, return the maximum score difference (Alice minus Bob).
Examples
Input: [-1,2,-3,4,-5]
Output: 5
Input: [7,-6,5,10,5,-2,-6]
Output: 13
Hints
Define `dp[i]` as the maximum score difference the current player can achieve from position `i` onward, assuming they must take at least 2 piles.
Precompute prefix sums. At position i, the player can take k piles (k >= 2). They get `prefix[i+k-1] - prefix[i-1]` minus the opponent's optimal advantage from position `i+k`.
This can be optimized to O(n) using suffix maximum DP. Let `best[i] = max(dp[i], best[i+1])` to avoid O(n^2) inner loop.
Related Problems
Stone Game VIII
Alice and Bob take turns removing stones from a row, with Alice going first.