NKLP - Hoán vị dài nhất
Tác giả: skyvn97
Ngôn ngữ: C++
#include<bits/stdc++.h>
using namespace std;
const int N = 100000;
int last[N], a[N], d[N], n;
void enter() {
cin >> n;
for(int i = 0; i < n; ++i)
cin >> a[i], --a[i];
}
void precal() {
fill(last, last+n, n);
d[n-1] = n; last[a[n-1]] = n-1;
for(int i = n-2; i >= 0; --i) {
d[i] = min(d[i+1], last[a[i]]);
last[a[i]] = i;
}
}
bool mark[N];
void solve() {
int res = 0, now = 0;
for(int i = 0, j = 0; i < n; ++i) {
while(j < d[i]) {
mark[a[j++]] = true;
while(now < n && mark[now]) ++now;
res = max(res, now);
}
mark[a[i]] = false;
now = min(now, a[i]);
}
cout << res << endl;
}
int main() {
ios::sync_with_stdio(false);
enter();
precal();
solve();
return 0;
}