// 演算法：區間 DP。dp[i][j] = 面對區間 [i..j] 的玩家能領先對手的淨分差。
// Algorithm: interval DP. dp[i][j] = net lead the player-to-move can get on piles[i..j].
// 轉移：拿左端得 piles[i]-dp[i+1][j]，拿右端得 piles[j]-dp[i][j-1]，取大者。
// Transition: take left -> piles[i]-dp[i+1][j], take right -> piles[j]-dp[i][j-1]; keep the max.
// 最後 dp[0][n-1] > 0 表示先手 Alice 淨領先 / final dp[0][n-1] > 0 means Alice leads.

#include <stdbool.h>   // 提供 bool / true / false / gives us bool, true, false
#include <stdlib.h>    // 提供 malloc 和 free / gives us malloc and free

bool stoneGame(int* piles, int pilesSize) {
    int n = pilesSize;                       // n 是石子堆數 / n = number of piles

    // 配置一個 n×n 的二維表。C 沒有內建二維陣列，我們用「指標的陣列」。
    // Allocate an n×n table. C has no built-in 2D array, so we use an array of pointers.
    int** dp = (int**)malloc(n * sizeof(int*));   // dp 是 n 個「int 指標」/ dp holds n int-pointers (rows)
    for (int i = 0; i < n; i++) {
        // calloc 配置一列 n 個 int 並全部初始化為 0 / calloc gives n ints, all zeroed
        dp[i] = (int*)calloc(n, sizeof(int));
    }

    // 基底：只剩一堆時，該玩家就拿走它，淨領先等於這堆的石子數。
    // Base case: with one pile left, the player takes it; net lead = that pile's stones.
    for (int i = 0; i < n; i++) {
        dp[i][i] = piles[i];                 // 對角線填入單堆的值 / fill the diagonal
    }

    // 依「區間長度」由小到大填表。len 從 2 開始，因為長度 1 已填好。
    // Fill by increasing interval length. Start at 2 since length 1 is done.
    for (int len = 2; len <= n; len++) {
        // i 是區間左端；j = i+len-1 是右端，不能超出陣列。
        // i is the left end; j = i+len-1 is the right end, must stay in bounds.
        for (int i = 0; i + len - 1 < n; i++) {
            int j = i + len - 1;             // 由左端和長度算出右端 / right end from left + length

            int takeLeft  = piles[i] - dp[i + 1][j];  // 拿左端後對手面對 [i+1..j] / after taking left, opponent faces [i+1..j]
            int takeRight = piles[j] - dp[i][j - 1];  // 拿右端後對手面對 [i..j-1] / after taking right, opponent faces [i..j-1]

            // 當前玩家選對自己較有利（淨領先較大）的那一步。
            // The current player picks whichever move gives the larger net lead.
            dp[i][j] = takeLeft > takeRight ? takeLeft : takeRight;
        }
    }

    bool aliceWins = dp[0][n - 1] > 0;       // 先手在整個區間上淨領先即獲勝 / first mover leads => wins

    // 手動釋放記憶體，避免記憶體洩漏。先釋放每一列，再釋放列指標本身。
    // Free memory manually to avoid leaks: free each row, then the array of row pointers.
    for (int i = 0; i < n; i++) free(dp[i]);
    free(dp);

    return aliceWins;                        // 回傳 Alice 是否獲勝 / return whether Alice wins
}