1140. Stone Game II Medium

1/**
2 * [1140] Stone Game II
3 *
4 * 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. 
5 * Alice and Bob take turns, with Alice starting first.  Initially, M = 1.
6 * 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).
7 * The game continues until all the stones have been taken.
8 * Assuming Alice and Bob play optimally, return the maximum number of stones Alice can get.
9 *  
10 * Example 1:
11 * 
12 * Input: piles = [2,7,9,4,4]
13 * Output: 10
14 * Explanation:  If Alice takes one pile at the beginning, Bob takes two piles, then Alice takes 2 piles again. Alice can get 2 + 4 + 4 = 10 piles in total. If Alice takes two piles at the beginning, then Bob can take all three piles left. In this case, Alice get 2 + 7 = 9 piles in total. So we return 10 since it's larger. 
15 * 
16 * Example 2:
17 * 
18 * Input: piles = [1,2,3,4,5,100]
19 * Output: 104
20 * 
21 *  
22 * Constraints:
23 * 
24 * 	1 <= piles.length <= 100
25 * 	1 <= piles[i] <= 10^4
26 * 
27 */
28pub struct Solution {}
29
30// problem: https://leetcode.com/problems/stone-game-ii/
31// discuss: https://leetcode.com/problems/stone-game-ii/discuss/?currentPage=1&orderBy=most_votes&query=
32
33// submission codes start here
34
35impl Solution {
36    pub fn stone_game_ii(piles: Vec<i32>) -> i32 {
37        0
38    }
39}
40
41// submission codes end
42
43#[cfg(test)]
44mod tests {
45    use super::*;
46
47    #[test]
48    fn test_1140() {
49    }
50}
51