1
class Solution {
2
  Integer[] dp;
3

4
  public String stoneGameIII(int[] stoneValue) {
5
    dp = new Integer[stoneValue.length + 1];
6

7
    Arrays.fill(dp, null);
8

9
    int ans = stoneGameIII(0, stoneValue);
10
    if (ans == 0) return "Tie";
11
    else if (ans > 0) return "Alice";
12
    else return "Bob";
13
  }
14

15
  public int stoneGameIII(int l, int[] s) {
16
    if (l >= s.length) return 0;
17
    if (dp[l] != null) return dp[l];
18
    int ans;
19
    ans = Integer.MIN_VALUE;
20
    if (l < s.length) {
21
      ans = Math.max(ans, s[l] - stoneGameIII(l + 1, s));
22
    }
23
    if (l + 1 < s.length) {
24
      ans = Math.max(ans, s[l] + s[l + 1] - stoneGameIII(l + 2, s));
25
    }
26
    if (l + 2 < s.length) {
27
      ans = Math.max(ans, s[l] + s[l + 1] + s[l + 2] - stoneGameIII(l + 3, s));
28
    }
29

30
    return dp[l] = ans;
31
  }
32
}