\(\mathrm{dp}[i]\) を、\(A_1, \dots, A_i\) の部分列であって条件を満たすもののうち、末尾の要素が \(A_i\) であるものの長さの最大値とします。答えは \(\mathrm{dp}[i]\) たちの最大値です。

\(\mathrm{dp}[i]\) からの遷移は、\(i < j\) かつ \(A_i + 1 = A_j\) を満たす \(j\) のうち最小のものに対して \(\mathrm{dp}[j] \leftarrow \max(\mathrm{dp}[j], \mathrm{dp}[i] + 1)\) とするもののみを考える（最小でない \(j\) に対する遷移を考えない）ことにしても問題ありません。このような \(j\) は \(A_i\) の値ごとに添字を並べた配列を作成し、その上を二分探索することで求められます。

時間計算量は全体で \(O(N \log N)\) です。

C++ による実装例：

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

int main()
{
  int N;
  cin >> N;
  vector<int> A(N);
  for (int i = 0; i < N; i++)
    cin >> A[i];

  map<int, vector<int>> mps;
  for (int i = 0; i < N; i++)
    mps[A[i]].push_back(i);

  vector<int> dp(N, 1);
  for (int i = 0; i < N; i++)
  {
    const auto &vec = mps[A[i] + 1];
    int k = ranges::lower_bound(vec, i) - vec.begin();
    if (k < (int)vec.size())
    {
      int j = vec[k];
      dp[j] = max(dp[j], dp[i] + 1);
    }
  }
  cout << ranges::max(dp) << endl;
}