1247. Stone Game II

HardDynamic ProgrammingGame Theory

Piles of stones are in a row. Alice and Bob alternate turns, starting with Alice, with M initially 1. On a turn a player takes all stones from the first X remaining piles where 1 <= X <= 2M, and then M becomes max(M, X). Assuming both play optimally, return the maximum stones Alice can collect. The input is JSON {piles}.

Input: JSON {piles}.

Output: Integer — the maximum stones Alice can get.

Examples

Example 1
Input: {"piles":[2,7,9,4,4]}
Output: 10
Explanation: Alice can secure 10 stones.
Example 2
Input: {"piles":[1,2,3,4,5,100]}
Output: 104
Explanation: Alice reaches the large pile.
Example 3
Input: {"piles":[5]}
Output: 5
Explanation: Alice takes everything.

Constraints

Asked by

AmazonGoogleMicrosoftMetaBloomberg
Solve this problem in the editor →