class Solution {
  Integer[] dp;
  int[] stones;
  public String stoneGameIII(int[] stoneValue) {
    this.stones = stoneValue;
    int total = 0;
    for (int s : stoneValue) {
      total += s;
    }
    dp = new Integer[stoneValue.length];
    int aliceShare = solve(0);
    int bobShare = total - aliceShare;
    if (aliceShare > bobShare) {
      return "Alice";
    } else if (bobShare > aliceShare) {
      return "Bob";
    }
    return "Tie";
  }

  public int solve(int index) {
    if (index >= stones.length) {
      return 0;
    }
    if (dp[index] != null) {
      return dp[index];
    }

    int sum = stones[index];
    int best = sum + minSolve(index + 1);
    for (int i = index + 1; i < Math.min(stones.length, index + 3); i++) {
      sum += stones[i];
      best = Math.max(best, sum + minSolve(i + 1));
    }

    dp[index] = best;
    return best;
  }

  public int minSolve(int index) {
    if (index >= stones.length) {
      return 0;
    }
    int worst = solve(index + 1);
    for (int i = index + 2; i <= Math.min(stones.length, index + 3); i++) {
      worst = Math.min(worst, solve(i));
    }
    return worst;
  }
}