\(f(l,r)=\max(A_l,\dots,A_r)-\min(A_l,\dots,A_r)\) と定めます。

考察

考えている区間が広くなると、最大値は大きく、最小値は小さくなるので、 \(f(l,r)\) は大きくなります。つまりある種の単調性があるので、「 \(f(l,r)\leq K\) となる \((l,r)\) は？」は、尺取法や二分探索を用いて高速に求められるかもしれないと見当をつけることができます。
実際にそれでうまく解けることを確かめます。

解法

\(A_l,\ldots,A_r\) を ordered multiset で持つことで、尺取法により求めることができ、 \(O(N\log N)\) で問題を解くことができます。

実装例 (C++)

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

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

  multiset<int>s;
  int l = 0;
  int ans = 0;
  for(int r=0; r<n; r++){
    s.insert(a[r]);
    while(true){
      int M = *prev(s.end());
      int m = *s.begin();
      if(M-m <= k){
        break;
      }
      s.erase(s.find(a[l]));
      l++;
    }
    ans = max(ans, r - l + 1);
  }

  cout << ans << endl;
}

実装例 (Python)

from sortedcontainers import SortedList
N, K = map(int, input().split())
A = list(map(int, input().split()))

S = SortedList()
l = 0
ans = 0
for r in range(N):
  S.add(A[r])
  while S[-1] - S[0] > K:
    S.discard(A[l])
    l += 1
  ans = max(ans, r - l + 1);
print(ans)

なお、尺取法は区間の操作が「左側を縮める・右側を伸ばす」だけであることから、ordered multiset の代わりに適切に deque を用いることでも最大値・最小値を管理することができ、この方針では \(O(N)\) で問題を解くことができます。

実装例 (Python)

from collections import deque

N, K = map(int, input().split())
A = list(map(int, input().split()))

Mq = deque()
mq = deque()
l = 0
ans = 0
for r in range(N):
  # max を管理する deque の更新
  while len(Mq) > 0 and Mq[-1][0] < A[r]:
    Mq.pop()
  Mq.append((A[r], r))
  # min をを管理する deque の更新
  while len(mq) > 0 and mq[-1][0] > A[r]:
    mq.pop()
  mq.append((A[r], r))
  # 区間の左端を縮める
  while Mq[0][0] - mq[0][0] > K:
    if Mq[0][1] == l:
      Mq.popleft()
    if mq[0][1] == l:
      mq.popleft()
    l += 1
  ans = max(ans, r - l + 1)

print(ans)