Loading problem…
Alice and Bob continue their games with piles of stones. There are a number of piles arranged in a row, and each pile has a **positive** integer number of stones `piles[i]`. The objective of the game is to end with the most stones. Alice and Bob take turns, with **Alice starting first**. Initially, `M = 1`. On each player's turn, that player can take **all the stones** in the **first** `X` remaining piles, where `1 <= X <= 2M`. Then, we set `M = max(M, X)`. The game continues until all the stones have been taken. Assuming Alice and Bob play **optimally**, return the maximum number of stones Alice can get.
Example 1
Input: piles = [2,7,9,4,4]
Output: 10
Explanation: Alice takes just the first pile (2). Bob takes the next two piles (7 and 9), because taking only 7 would let Alice take 9 and 4. Alice then takes the last two piles (4 and 4). Alice ends with 2 + 4 + 4 = 10.
Example 2
Input: piles = [1,2,3,4,5,100]
Output: 104
Explanation: Alice takes 1, Bob takes 2, and Alice takes 3, which keeps the maximum take small. Bob can then take at most two piles (4 and 5), which leaves the 100 pile for Alice. She ends with 1 + 3 + 100 = 104.
Example 3
Input: piles = [1,2]
Output: 3
Explanation: With M = 1 Alice may take up to 2 piles, so she takes both and gets all 3 stones.
The state is (i, M): the game faces piles[i:] and the current player may grab 1..2M piles. Maximizing your own stones equals maximizing suffix[i] minus whatever the opponent then guarantees from the smaller state. Fill dp bottom-up over i (right to left) and every M.
Run checks all cases above. Submit evaluates all test cases.