// 演算法：記憶化 DP。dp[i] = 從 i 出發最多造訪的索引數。
// Algorithm: memoized DP. dp[i] = max indices visited starting at i.
// 往兩側各掃最多 d 步，碰到 >= arr[i] 的高度就停（被擋住）。答案 = max(dp[i])。
// Scan up to d steps each side, stopping at any height >= arr[i] (blocked). Answer = max(dp[i]).

#include <stdlib.h>   // 提供 calloc / free / NULL / Provides calloc / free / NULL

// 遞迴計算 dp[i]，結果存進 memo / Recursively compute dp[i], caching in memo
int dfs(int i, int* arr, int n, int d, int* memo) {
    if (memo[i] != 0) return memo[i];   // 已算過就直接回傳（dp 永遠 >=1，0 代表未算）/ cached? return it (dp is always >=1, so 0 means "not computed")

    int best = 1;                       // 至少能造訪自己這個索引 / at minimum we visit index i itself

    // 往右掃：x 從 1 到 d，且不超出邊界 / scan right: x = 1..d, staying in bounds
    for (int x = 1; x <= d && i + x < n; x++) {
        int j = i + x;                  // 候選目標索引 / candidate target index
        if (arr[j] >= arr[i]) break;    // 遇到不矮於 arr[i] 的高度就停：要嘛跳不過去，要嘛它擋住後面 / hit a height >= arr[i]: either illegal target or a blocker — stop
        int sub = 1 + dfs(j, arr, n, d, memo); // 從 j 繼續，再加上 i 這一步 / continue from j, plus the step into i
        if (sub > best) best = sub;     // 取較大的路徑長度 / keep the longer reach
    }

    // 往左掃：對稱地處理 / scan left: symmetric handling
    for (int x = 1; x <= d && i - x >= 0; x++) {
        int j = i - x;                  // 候選目標索引（左側）/ candidate target on the left
        if (arr[j] >= arr[i]) break;    // 同樣遇到障礙就停 / stop at the first blocker
        int sub = 1 + dfs(j, arr, n, d, memo);
        if (sub > best) best = sub;
    }

    memo[i] = best;                     // 存起來，下次直接用 / cache so we never recompute
    return best;
}

int maxJumps(int* arr, int arrSize, int d) {
    // calloc 配置 arrSize 個 int 並全部設為 0（代表「尚未計算」）/ allocate arrSize ints, all zeroed (meaning "not yet computed")
    int* memo = (int*)calloc(arrSize, sizeof(int));

    int ans = 0;                        // 目前找到的最大造訪數 / best answer so far
    for (int i = 0; i < arrSize; i++) { // 嘗試以每個索引為起點 / try every index as a starting point
        int r = dfs(i, arr, arrSize, d, memo);
        if (r > ans) ans = r;           // 更新全域最大值 / update the global maximum
    }

    free(memo);                         // 歸還記憶體，避免外洩 / release memory to avoid a leak
    return ans;
}