// 演算法：DP，dp[j] = 從索引 0 跳到 j 的最大次數，-1 表不可達
// Algorithm: DP where dp[j] = max jumps from 0 to j, -1 means unreachable.
// 對每個 j，掃所有 i<j，若 |nums[j]-nums[i]|<=target 則用 dp[i]+1 鬆弛 dp[j]
// For each j, scan every i<j and relax dp[j] = max(dp[j], dp[i]+1) when in range.
// 時間 O(n^2)，空間 O(n)。Time O(n^2), space O(n).

#include <stdlib.h>   // malloc / free 的標頭 / header for malloc and free

int maximumJumps(int* nums, int numsSize, int target) {
    // 在堆積上配置長度為 n 的 int 陣列 / allocate an int array of length n on the heap
    int* dp = (int*)malloc(sizeof(int) * numsSize);

    // 把全部位置先設為 -1，代表「目前還無法從 0 跳到這裡」
    // Initialize every entry to -1, meaning "not yet known to be reachable from 0".
    for (int i = 0; i < numsSize; i++) {
        dp[i] = -1;
    }
    dp[0] = 0;  // 起點本身不需要跳，所以是 0 / starting point needs zero jumps

    // 外層 j：依序計算每個目標索引；因為只往回看 i<j，順序保證子問題已算好
    // Outer loop j: compute each target index in order; since we only look back at i<j,
    // every dp[i] we read has already been finalized.
    for (int j = 1; j < numsSize; j++) {
        // 內層 i：列舉所有可能跳到 j 的前一格 / inner loop: every candidate previous index
        for (int i = 0; i < j; i++) {
            // 若 i 本身就跳不到，當然不能從 i 再跳到 j / skip unreachable predecessors
            if (dp[i] == -1) continue;

            // 用 long 避免兩個 ±1e9 相減在 int 邊界附近的疑慮 (純為教學保險)
            // Use long to dodge any int-edge worries when subtracting two ±1e9 values.
            long diff = (long)nums[j] - (long)nums[i];

            // 條件：差值落在 [-target, target] 區間 / jump is legal iff diff is in range
            if (diff >= -(long)target && diff <= (long)target) {
                // 鬆弛：dp[j] 取「自己」與「從 i 過來再 +1」中較大者
                // Relax: keep the larger of the current dp[j] and dp[i]+1.
                if (dp[i] + 1 > dp[j]) {
                    dp[j] = dp[i] + 1;
                }
            }
        }
    }

    int ans = dp[numsSize - 1];  // 終點的答案（可能仍是 -1）/ answer at the last index
    free(dp);                    // 釋放剛剛 malloc 的記憶體 / release heap memory
    return ans;
}