// 演算法 / Algorithm: 後綴 DP（博弈 minimax）。
// dp[i] = 當前玩家面對石頭 i..n-1 時能保證的最佳「分數差」(自己 − 對手)。
// dp[i] = max_{k=1..3} ( 前 k 顆的和 − dp[i+k] )，dp[n] = 0；看 dp[0] 的正負決定勝負。
// Suffix DP: dp[i] is the best (self − opponent) score difference from stones i..n-1.

#include <stdlib.h>   // malloc / free — 動態配置記憶體 / dynamic memory
#include <limits.h>   // LONG_MIN — long 的最小值，當「還沒有最佳值」的起點 / sentinel for "no best yet"

char* stoneGameIII(int* stoneValue, int stoneValueSize) {
    int n = stoneValueSize;                       // n = 石頭數量 / number of stones

    // dp 有 n+1 格：dp[n] 是邊界，其餘 dp[0..n-1] 是各後綴的答案。
    // dp needs n+1 slots: dp[n] is the base case, dp[0..n-1] hold suffix answers.
    // 用 long 避免加總溢位（最多 5e4 顆 × 1000 = 5e7，int 其實夠，但 long 更保險）。
    // Use long to be safe against overflow when summing values.
    long *dp = (long*)malloc(sizeof(long) * (n + 1));

    dp[n] = 0;                                     // 沒有石頭時差值為 0 / no stones left → difference 0

    // 從後往前填表：算 dp[i] 時 dp[i+1..n] 都已就緒。
    // Fill right-to-left so dp[i+1..n] are ready when computing dp[i].
    for (int i = n - 1; i >= 0; i--) {
        long take = 0;                             // take = 目前這一步累計取走的石頭和 / running sum of stones taken this move
        long best = LONG_MIN;                      // best = 目前試過選項中最好的差值 / best difference seen so far

        // k 從 0 開始：k=0 代表取 1 顆、k=1 取 2 顆、k=2 取 3 顆；i+k<n 確保不越界。
        // k=0,1,2 means taking 1,2,3 stones; the i+k<n guard prevents reading past the end.
        for (int k = 0; k < 3 && i + k < n; k++) {
            take += stoneValue[i + k];             // 把第 (i+k) 顆加進本步總和 / add stone (i+k) to this move's sum
            long cur = take - dp[i + k + 1];       // 本步得分 − 對手接手後的最佳差值 / my gain minus opponent's best on the rest
            if (cur > best) best = cur;            // 保留最好的選擇 / keep the best choice
        }
        dp[i] = best;                              // 記錄面對後綴 i 的最佳差值 / store best difference for suffix i
    }

    long res = dp[0];                              // res = 遊戲一開始 Alice 的最佳差值 / Alice's best difference for the whole game
    free(dp);                                      // 歸還記憶體，避免洩漏 / release memory to avoid a leak

    // 差值 > 0 → Alice 分數較高；< 0 → Bob 較高；= 0 → 平手。
    // difference > 0 → Alice higher; < 0 → Bob higher; = 0 → tie.
    if (res > 0) return "Alice";                   // 回傳字串常值即可（LeetCode 接受）/ returning a string literal is fine here
    if (res < 0) return "Bob";
    return "Tie";
}