1872. Stone Game VIII Hard

1/**
2 * [1872] Stone Game VIII
3 *
4 * Alice and Bob take turns playing a game, with Alice starting first.
5 * 
6 * There are n stones arranged in a row. On each player's turn, while the number of stones is more than one, they will do the following:
7 * 
8 * <ol>
9 * 	Choose an integer x > 1, and remove the leftmost x stones from the row.
10 * 	Add the sum of the removed stones' values to the player's score.
11 * 	Place a new stone, whose value is equal to that sum, on the left side of the row.
12 * </ol>
13 * 
14 * The game stops when only one stone is left in the row.
15 * 
16 * The score difference between Alice and Bob is (Alice's score - Bob's score). Alice's goal is to maximize the score difference, and Bob's goal is the minimize the score difference.
17 * 
18 * Given an integer array stones of length n where stones[i] represents the value of the i^th stone from the left, return the score difference between Alice and Bob if they both play optimally.
19 * 
20 *  
21 * Example 1:
22 * 
23 * 
24 * Input: stones = [-1,2,-3,4,-5]
25 * Output: 5
26 * Explanation:
27 * - Alice removes the first 4 stones, adds (-1) + 2 + (-3) + 4 = 2 to her score, and places a stone of
28 *   value 2 on the left. stones = [2,-5].
29 * - Bob removes the first 2 stones, adds 2 + (-5) = -3 to his score, and places a stone of value -3 on
30 *   the left. stones = [-3].
31 * The difference between their scores is 2 - (-3) = 5.
32 * 
33 * 
34 * Example 2:
35 * 
36 * 
37 * Input: stones = [7,-6,5,10,5,-2,-6]
38 * Output: 13
39 * Explanation:
40 * - Alice removes all stones, adds 7 + (-6) + 5 + 10 + 5 + (-2) + (-6) = 13 to her score, and places a
41 *   stone of value 13 on the left. stones = [13].
42 * The difference between their scores is 13 - 0 = 13.
43 * 
44 * 
45 * Example 3:
46 * 
47 * 
48 * Input: stones = [-10,-12]
49 * Output: -22
50 * Explanation:
51 * - Alice can only make one move, which is to remove both stones. She adds (-10) + (-12) = -22 to her
52 *   score and places a stone of value -22 on the left. stones = [-22].
53 * The difference between their scores is (-22) - 0 = -22.
54 * 
55 * 
56 *  
57 * Constraints:
58 * 
59 * 
60 * 	n == stones.length
61 * 	2 <= n <= 10^5
62 * 	-10^4 <= stones[i] <= 10^4
63 * 
64 */
65pub struct Solution {}
66
67// problem: https://leetcode.com/problems/stone-game-viii/
68// discuss: https://leetcode.com/problems/stone-game-viii/discuss/?currentPage=1&orderBy=most_votes&query=
69
70// submission codes start here
71
72impl Solution {
73    pub fn stone_game_viii(stones: Vec<i32>) -> i32 {
74        0
75    }
76}
77
78// submission codes end
79
80#[cfg(test)]
81mod tests {
82    use super::*;
83
84    #[test]
85    fn test_1872() {
86    }
87}
88