NKLP - Hoán vị dài nhất
Tác giả: ladpro98
Ngôn ngữ: C++
#include <bits/stdc++.h>
const int N = 100005;
using namespace std;
int res, n, a[N], pos[N];
void Play(int len) {
int mi = n, ma = 0;
for(int i=1; i<=len; i++) {
if (pos[i] == 0) break;
mi = min(mi, pos[i]);
ma = max(ma, pos[i]);
if (ma - mi == i-1)
res = max(res, i);
}
}
int main()
{
//freopen("NKLP.in", "r", stdin);
scanf("%d\n", &n);
int i, l, r;
for(i=1; i<=n; i++) scanf("%d", &a[i]);
n++;a[n] = a[n-1]; l = 1;
for(r=1; r<=n; r++) {
if (pos[a[r]]>0) {
if (res < r-l) Play(r-l);
while (a[l] != a[r]) {
pos[a[l]] = 0; l++;
}l++;
}
pos[a[r]] = r;
}
printf("%d", res);
return 0;
}