この問題はセグメントツリーを用いて解くことができます。

\(\mathrm{DP}[i][x]\) を「 \(i\) 番目の作品までを選ぶか選ばないか決め、最後に選んだ作品のスコアが \(x\) であるときの、選んだ個数の最大値」とします。このとき、

\(\mathrm{DP}[i+1][x]=\begin{cases} 1+\max_{|x-y|\leq D}\mathrm{DP}[i][y] & x= H_i\\ \mathrm{DP}[i][x] & x\neq H_i\\ \end{cases}\)

となります。このDPテーブルをそのまま計算することはできません。高速化を考えます。

\(\mathrm{DP}[i]\) と \(\mathrm{DP}[i+1]\) の違いは高々 \(1\) 箇所です。そこで、 \(i\) をDPのキーとして持つことをやめ、

for i in 1..N:
  dp[H[i]] <- 1 + max{dp[y] | abs(x-y)<=D}

として in-place に計算することができます。ここで、\(dp\) テーブルに意味のある値が入るのは、キーが \(H\) に含まれるときに限るので \(O(N)\) 箇所です。よって、この式のまま計算すると \(\Theta(N^2)\) で計算できます。右辺でmaxを取る範囲が区間となっているので、座標圧縮のうえ区間maxを取得できるセグメントツリーにDPテーブルを乗せることで高速化でき、全体で \(O(N\log N)\) で計算できます。

実装例 (C++)

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

int op(int x, int y){return max(x, y);}
int e(){return 0;}

int main(){
  int n, d;
  cin >> n >> d;
  vector<int>h(n);
  for(int i=0; i<n; i++) cin >> h[i];

  // 座標圧縮
  vector<int>i2v = h;
  sort(i2v.begin(), i2v.end());
  i2v.erase(unique(i2v.begin(), i2v.end()), i2v.end());
  unordered_map<int, int>v2i;
  for(int i=0; i<i2v.size(); i++){
   v2i[i2v[i]] = i;
  }

  atcoder::segtree<int,op,e>seg(n);
  for(int i=0; i<n; i++){
    int left = lower_bound(i2v.begin(), i2v.end(), h[i]-d) - i2v.begin();
    int right = lower_bound(i2v.begin(), i2v.end(), h[i]+d+1) - i2v.begin();
    int val = seg.prod(left, right);
    seg.set(v2i[h[i]], val+1);
  }
  cout << seg.all_prod() << endl;
}

実装例 (Python)

import bisect
from atcoder.segtree import SegTree

N, D = map(int, input().split())
H = list(map(int, input().split()))

# 座標圧縮
i2v = sorted(set(H))
v2i = {v:i for i, v in enumerate(i2v)}

seg = SegTree(max, 0, N)
for h in H:
  left = bisect.bisect_left(i2v, h-D)
  right = bisect.bisect_left(i2v, h+D+1)
  val = seg.prod(left, right)
  seg.set(v2i[h], val+1)

print(seg.all_prod())