325. Stone Game II

MediumDynamic Programming

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.

Examples

Input: [2,7,9,4,4]

Output: 10

Explanation: If Alice grabs 2 piles first she opens the door for Bob to grab the big middle piles; taking just the first pile (2) and responding optimally nets her 2 + 4 + 4 = 10.

Constraints

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

Run checks all cases above. Submit evaluates all test cases.