\(d[i][v]\) を「\(A_1\) から \(A_i\) までの連続部分列のみを考えた時に、末尾の要素が \(v\) であるような条件を満たす部分列の長さの最大値」とします。求める答えは \(d[i][v]\) の最大値です。

この動的計画法の遷移を考えると、\(d[i][v]\) は \(v=A_i\) なら \(d[i][v]=\max(d[i-1][v], d[i-1][v-1]+1)\)、 \(v\neq A_i\) なら \(d[i][v]=d[i-1][v]\) となります。

\(d[i]\) を in-place に更新する（配列を使い回す）ことにし、さらに要素が非ゼロである部分のみ map で持ちながら動的計画法の更新を行うことで計算量 \(O(N \log N)\) で解くことができます。

以上を適切に実装することでこの問題を解くことができます。詳しくは実装例を参考にしてください。

実装例(Python3)

from collections import defaultdict

n = int(input())
a = list(map(int, input().split()))
d = defaultdict(int)
for v in a:
    d[v] = max(d[v], d[v - 1] + 1)
print(max(d.values()))

実装例(C++)

#include <bits/stdc++.h>
using namespace std;
int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n;
	cin >> n;
	unordered_map<int, int> d;
	int ans = 0;
	for (int i = 0; i < n; i++) {
		int ai;
		cin >> ai;
		d[ai] = max(d[ai], d[ai - 1] + 1);
		ans = max(ans, d[ai]);
	}
	cout << ans << endl;
}