1406. Stone Game III Hard

1/**
2 * [1406] Stone Game III
3 *
4 * Alice and Bob continue their games with piles of stones. There are several stones arranged in a row, and each stone has an associated value which is an integer given in the array stoneValue.
5 * Alice and Bob take turns, with Alice starting first. On each player's turn, that player can take 1, 2, or 3 stones from the first remaining stones in the row.
6 * The score of each player is the sum of the values of the stones taken. The score of each player is 0 initially.
7 * The objective of the game is to end with the highest score, and the winner is the player with the highest score and there could be a tie. The game continues until all the stones have been taken.
8 * Assume Alice and Bob play optimally.
9 * Return "Alice" if Alice will win, "Bob" if Bob will win, or "Tie" if they will end the game with the same score.
10 *  
11 * Example 1:
12 * 
13 * Input: values = [1,2,3,7]
14 * Output: "Bob"
15 * Explanation: Alice will always lose. Her best move will be to take three piles and the score become 6. Now the score of Bob is 7 and Bob wins.
16 * 
17 * Example 2:
18 * 
19 * Input: values = [1,2,3,-9]
20 * Output: "Alice"
21 * Explanation: Alice must choose all the three piles at the first move to win and leave Bob with negative score.
22 * If Alice chooses one pile her score will be 1 and the next move Bob's score becomes 5. In the next move, Alice will take the pile with value = -9 and lose.
23 * If Alice chooses two piles her score will be 3 and the next move Bob's score becomes 3. In the next move, Alice will take the pile with value = -9 and also lose.
24 * Remember that both play optimally so here Alice will choose the scenario that makes her win.
25 * 
26 * Example 3:
27 * 
28 * Input: values = [1,2,3,6]
29 * Output: "Tie"
30 * Explanation: Alice cannot win this game. She can end the game in a draw if she decided to choose all the first three piles, otherwise she will lose.
31 * 
32 *  
33 * Constraints:
34 * 
35 * 	1 <= stoneValue.length <= 5 * 10^4
36 * 	-1000 <= stoneValue[i] <= 1000
37 * 
38 */
39pub struct Solution {}
40
41// problem: https://leetcode.com/problems/stone-game-iii/
42// discuss: https://leetcode.com/problems/stone-game-iii/discuss/?currentPage=1&orderBy=most_votes&query=
43
44// submission codes start here
45
46impl Solution {
47    pub fn stone_game_iii(stone_value: Vec<i32>) -> String {
48        String::new()
49    }
50}
51
52// submission codes end
53
54#[cfg(test)]
55mod tests {
56    use super::*;
57
58    #[test]
59    fn test_1406() {
60    }
61}
62