1140. Stone Game II

Practice Stone Game II for free on NudgeCode: Medium, Dynamic Programming pattern. Write it in Python or JavaScript, run the tests in your browser, and ask for a hint when you are stuck.

Piles of stones stand in a row with sizes piles. Alice and Bob alternate turns, Alice first, and a number M starts at 1. On a turn the player takes all stones from the first X remaining piles, where 1 <= X <= 2M, and then M becomes max(M, X). The game ends when all piles are taken. If both players try to collect as many stones as they can, return the number of stones Alice ends with.

Example

piles = [2,7,9,4,4]        ->  10
piles = [1,2,3,4,5,100]    ->  104

Constraints

• 1 <= piles.length <= 100
• 1 <= piles[i] <= 10^4