NKLP - Hoán vị dài nhất
Tác giả: flashmt
Ngôn ngữ: C++
#include <iostream>
#include <algorithm>
#include <cstdio>
using namespace std;
int n, a[100100], pos[100100], prev[100100], next[100100];
int solve()
{
int res = 0;
for (int i = 0; i <= n; i++) pos[i] = -1;
for (int i = 0; i < n; i++)
{
prev[i] = pos[a[i]];
if (pos[a[i]] >= 0) next[pos[a[i]]] = i;
pos[a[i]] = i;
}
for (int i = 0; i < n; i++)
if (pos[a[i]] >= 0) next[pos[a[i]]] = n;
for (int i = 0; i < n; i++)
if (a[i] == 1)
{
res = max(res, 1);
int R = i, bound = next[i], mx = 1;
for (int j = i - 1; j >= 0 && next[j] > i; j--)
{
bound = min(bound, next[j]);
R = min(R, next[j] - 1);
mx = max(mx, a[j]);
if (mx <= res || bound - j < mx) continue;
while (R - j + 1 < mx && R + 1 < bound && a[R + 1] < mx) R++;
if (R - j + 1 == mx) res = mx;
}
}
return res;
}
int main()
{
cin >> n;
for (int i = 0; i < n; i++) scanf("%d", a + i);
int ans = solve();
reverse(a, a + n);
ans = max(ans, solve());
cout << ans << endl;
}