Maximize Stones Taken With a Growing Move Window
Two players alternately take stones from the front of a row of piles. On each turn a player may take the next X piles where 1 <= X <= 2M, and M grows to max(M, X). Both play optimally; report the first player's best total.
Problem
Given an array piles where piles[i] is the stone count of pile i, players alternate turns starting with player 1. On a turn with current M, the active player takes the first X remaining piles for any 1 <= X <= 2M, then M becomes max(M, X). Both maximize their own stones. Return the maximum stones player 1 can collect.
Input
An integer array piles.
Output
An integer: the maximum stones for player 1.
Constraints
- 1 <= piles.length <= 100
- 1 <= piles[i] <= 10^4
- Both players play optimally.
Examples
Example 1
Input
piles = [2,7,9,4,4]
Output
10
Optimal play lets player 1 collect 10 stones.
Example 2
Input
piles = [1,2,3,4,5,100]
Output
104
Player 1 can secure 104 by controlling the window growth.