// 演算法 / Algorithm:
// 用區間 DP 追蹤「分數差」。dp[i][j] = 當只剩 nums[i..j]、輪到某玩家先取時，
// 他能保證的 (自己分數 - 對手分數) 的最大值。轉移取左或取右兩種選擇的較大者。
// Interval DP over score difference; dp[i][j] = best (my - opponent) score gap
// the mover can guarantee on nums[i..j]. Answer is dp[0][n-1] >= 0.

#include <stdbool.h>   // 讓 bool / true / false 可用 / brings in bool, true, false

bool predictTheWinner(int* nums, int numsSize) {
    int n = numsSize;                 // n 是陣列長度，寫短一點方便閱讀 / array length, short alias

    // dp 是二維表格；n <= 20 所以固定開 20x20 綽綽有餘
    // dp is a 2D table; n <= 20 so a fixed 20x20 array is plenty
    int dp[20][20];

    // Base case：子陣列只有一個元素時，先取者直接拿走它，差值就是該值本身
    // Base case: on a length-1 subarray the mover just takes it; the gap is that value
    for (int i = 0; i < n; i++)       // 逐一設定對角線 dp[i][i] / fill the diagonal
        dp[i][i] = nums[i];

    // 依子陣列長度 len 由小到大填表，確保用到的較短區間都已算好
    // Fill by increasing length so shorter subarrays (which we depend on) are ready
    for (int len = 2; len <= n; len++) {
        // i 是子陣列左端點；j = i+len-1 是右端點，需保證 j 不越界
        // i is the left end; j = i+len-1 is the right end, kept in-bounds
        for (int i = 0; i + len - 1 < n; i++) {
            int j = i + len - 1;      // 右端點索引 / right endpoint index

            // 選擇 A：取走左端 nums[i]，剩 nums[i+1..j] 留給對手，
            // 對手優勢 dp[i+1][j] 就是我的劣勢，故差值 = nums[i] - dp[i+1][j]
            // Option A: take nums[i]; opponent's edge dp[i+1][j] is my loss
            int pickLeft  = nums[i] - dp[i + 1][j];

            // 選擇 B：取走右端 nums[j]，剩 nums[i..j-1] 留給對手，同理
            // Option B: take nums[j]; symmetric reasoning
            int pickRight = nums[j] - dp[i][j - 1];

            // 當前玩家選對自己最有利（差值最大）的那一種 / mover picks the larger gap
            dp[i][j] = pickLeft > pickRight ? pickLeft : pickRight;
        }
    }

    // 整個陣列 nums[0..n-1] 上先手（玩家 1）的最佳差值 >= 0 就代表不會輸
    // If player 1's best gap over the whole array is >= 0, they don't lose
    return dp[0][n - 1] >= 0;
}