All problems

Stone Game II

Medium · dynamic programming

A row of coin piles lies on a table. piles[i] is the number of coins in the i-th pile, counting from the left. Two players, Ana and Ben, take turns, and Ana goes first.

A number M is kept during the game and starts at 1. On their turn, a player chooses any whole number X with 1 <= X <= 2 * M (and no larger than the number of piles left), then takes all the coins from the X leftmost piles that remain. After that, M becomes the larger of M and X.

The game ends when no piles are left. Each player plays to finish with as many coins as possible.

Return the total number of coins Ana collects when both players play perfectly.

Examples

Example 1

Input: piles = [5, 3, 1, 4, 2, 6]

Output: 12

There are 21 coins in all. With best play from both sides Ana ends with 12 and Ben with 9.

Example 2

Input: piles = [1, 1, 1, 1]

Output: 2

Each player ends up with two coins.

Example 3

Input: piles = [9]

Output: 9

There is only one pile and Ana takes it.

Constraints