// 演算法與 C 版相同：dp[j] 為從 0 到 j 的最大跳躍次數，-1 表不可達
// Same algorithm as the C version: dp[j] = max jumps from 0 to j, -1 = unreachable.
// 用 std::vector 與 std::max 寫得更簡潔 / written with std::vector and std::max for clarity.
// 時間 O(n^2)，空間 O(n)。Time O(n^2), space O(n).

#include <vector>     // std::vector 動態陣列 / dynamic array container
#include <algorithm>  // std::max
using namespace std;

class Solution {
public:
    int maximumJumps(vector<int>& nums, int target) {
        int n = nums.size();  // n 是陣列長度，型別 int 已足夠 / array length, int suffices

        // vector<int> dp(n, -1)：建立長度 n 的向量，每格初始化為 -1（不可達哨兵）
        // vector<int> dp(n, -1) creates a length-n vector, every slot set to -1 (sentinel).
        vector<int> dp(n, -1);
        dp[0] = 0;  // 起點不用跳 / starting index needs no jumps

        // 由小到大計算每個目標索引 j / fill dp[j] in increasing order of j
        for (int j = 1; j < n; ++j) {
            for (int i = 0; i < j; ++i) {
                if (dp[i] == -1) continue;  // i 不可達就跳過 / skip unreachable i

                // 轉成 long long，徹底避免兩個 1e9 量級整數相減/比較的溢位疑慮
                // Cast to long long to be completely safe against int overflow concerns.
                long long diff = (long long)nums[j] - (long long)nums[i];

                if (diff >= -(long long)target && diff <= (long long)target) {
                    // std::max 回傳兩者較大值，等同於手寫的 if 判斷
                    // std::max returns the larger of the two arguments.
                    dp[j] = max(dp[j], dp[i] + 1);
                }
            }
        }

        return dp[n - 1];  // 若仍為 -1 表示無法到達 / -1 means terminal index unreachable
    }
};