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

Download