Problem

Alex and Lee 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.

Alex and Lee take turns, with Alex 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 Alex and Lee play optimally, return the maximum number of stones Alex can get.

Example 1:

Input: piles = [2, 7, 9, 4, 4]
Output: 10
Explanation: 
If Alex takes one pile at the beginning, Lee takes two piles, 
then Alex takes 2 piles again. 
Alex can get 2 + 4 + 4 = 10 piles in total. 
If Alex takes two piles at the beginning, 
then Lee can take all three piles left. 
In this case, Alex get 2 + 7 = 9 piles in total. 
So we return 10 since it's larger.

Constraints:

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

问题描述

给定一个数组 piles 及正整数 M = 1，Alex 和 Lee 分别从头按顺序取 piles 中的元素。在每一轮中，他们可以取 1 <= x <= 2M 个元素，同时 M 变为 M = max(x, M)。假设他们都做最优的操作，求 Alex 获取到的元素的和。

备注

1. piles 的长度在 1 到 100 之间
2. piles 中的每个元素在 1 到 10^4 之间

样例

输入: piles = [2, 7, 9, 4, 4]
输出: 10
解释:
假设 Alex 拿 2，则 Lee 最优拿 7、9，Alex 拿 4、4，此时 Alex 总共拿了 10
假设 Alex 拿 2、7，则 Lee 最优拿 9、4、4，此时 Alex 总共拿了 9
Alex 最优拿到 10

解法 1

这道题 Alex 和 Lee 分别从头按顺序取 piles 中的元素，每一次取元素的多少不仅影响到下一次对方取的元素，同时还影响到对方可以取元素的数量。对于这样的问题，我们应该采用枚举的方式，可以采用深度优先遍历的方法。