Let \(dp_{i,j}\) be the maximum length of a subsequence of \((A_1, A_2, \dots, A_i)\) whose adjacent terms differ at most by \(D\) and last term is \(j\).

Then it holds that

\( dp_{i,j} = \begin{cases} \displaystyle\max_{k \in [A_i-D, A_i + D]} dp_{i - 1, k} + 1 & (j = A_i) \\ dp_{i-1,j} & (j \neq A_i). \end{cases}\)

If you follow this equation to fill the DP (Dynamic Programming) array, you can obtain the correct answer, but the time and spacial complexity would be \(\Theta(N^2)\).

Instead, we use the fact that \(dp_{i - 1,j}\) and \(dp_{i,j}\) coincides for almost all \(j\).

Instead of explicitly maintaining \(dp_{i,j}\) for each \((i,j)\), one can reuse an array, so that the DP above can be evaluated by maintaining a one-dimensional array \(dp\) and, for \(i = 1, 2, \ldots, N\) in this order, replacing \(dp_j\) with \(\displaystyle\max_{k \in [A_i-D, A_i + D]} dp_k + 1\).

This way, the spacial complexity is reduced to \(O(N)\). While the time complexity is still \(\Theta(N^2)\), one can use a segment tree that allows segment-max and element-update to reduce it to \(O(N \log N)\).

Sample code

#include <bits/stdc++.h>
using namespace std;

#include <atcoder/all>

int op(int a, int b) { return max(a, b); }
int e() { return 0; }

const int A = 500010;

int main() {
    int n, d;
    cin >> n >> d;
    vector<int> a(n);
    for (int &e : a) cin >> e;
    atcoder::segtree<int, op, e> seg(A);
    for (int e : a) {
        int l = max(0, e - d);
        int r = min(A - 1, e + d);
        int mx = seg.prod(l, r + 1);
        seg.set(e, mx + 1);
    }
    cout << seg.all_prod() << '\n';
}