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;
}

Download