Stone Game II

The key idea

Both players are greedy on the SAME total, so what one player leaves behind, the other takes. Define dp(i, M) = the most stones the player to move can get from piles[i:] given the current M. The mover picks X (1..2M) piles, and the opponent then faces dp(i+X, max(M, X)). Because every remaining stone goes to one of the two, the mover keeps suffix[i] - dp(i+X, ...) — maximize over X.

Problem

Alice and Bob continue their stones game. There are n piles of stones arranged in a row; the i-th pile has piles[i] stones. The objective 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 <= 2 * M. Then, M becomes max(M, X).

The game continues until all the stones have been taken. Assuming both players play optimally, return the maximum number of stones Alice can get.

Constraints

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

Examples

Input: piles = [2,7,9,4,4] Output: 10

Input: piles = [1,2,3,4,5,100] Output: 104

Input: piles = [2,4,5] Output: 6

Complexity

Time: O(n^3) Space: O(n^2)

See the full solution

✓Full worked approach
✓Reference code in 5 languages
✓Problem-solving tips
✓Step-by-step animated visualization

410310

Step-by-step visualization

Start free →