\(dp_{i,j}\) を隣接する \(2\) 項の差の絶対値が \(D\) 以下かつ末尾が \(j\) であるような \((A_1, A_2, \dots, A_i)\) の部分列の長さの最大値とします。

このとき、

\( 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}\)

が成立します。この式に従って dp 配列を計算すると、正しい答えは得られますが時間計算量および空間計算量が \(\Theta(N^2)\) となってしまいます。

そこで、\(dp_{i - 1,j}\) と \(dp_{i,j}\) の値がほとんどの \(j\) で一致することを用いて高速化を行います。

\(dp_{i,j}\) を 各 \((i,j)\) について陽に持つのではなく配列の使い回しをすることで、上の dp は \(1\) 次元配列 \(dp\) を持ち、\(i = 1, 2, \ldots, N\) の順で \(dp_j\) を \(\displaystyle\max_{k \in [A_i-D, A_i + D]} dp_k + 1\) で置き換えるというように書き換えられます。

これで空間計算量は \(O(N)\) となりました。時間計算量は max を愚直に計算すると \(\Theta(N^2)\) のままですが、区間 max 一点更新の segtree を用いることで \(O(N \log N)\) となります。

実装例

#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';
}