石子游戏 III

/*
 * 思路：我们使用动态规划和Java Stream来简化代码。使用一个dp数组来记录从当前索引到末尾的最大得分。
 */
import java.util.Arrays;

public class StoneGameIIIStream {
    public String stoneGameIII(int[] stoneValue) {
        int n = stoneValue.length;
        int[] dp = new int[n + 1];
        Arrays.fill(dp, Integer.MIN_VALUE);
        dp[n] = 0;
        for (int i = n - 1; i >= 0; i--) {
            int takeOne = stoneValue[i] - dp[i + 1];
            int takeTwo = (i + 1 < n) ? stoneValue[i] + stoneValue[i + 1] - dp[i + 2] : Integer.MIN_VALUE;
            int takeThree = (i + 2 < n) ? stoneValue[i] + stoneValue[i + 1] + stoneValue[i + 2] - dp[i + 3] : Integer.MIN_VALUE;
            dp[i] = Math.max(takeOne, Math.max(takeTwo, takeThree));
        }
        int aliceScore = dp[0];
        int totalScore = Arrays.stream(stoneValue).sum();
        int bobScore = totalScore - aliceScore;
        return aliceScore > bobScore ? "Alice" : aliceScore < bobScore ? "Bob" : "Tie";
    }
}