NKLP - Hoán vị dài nhất
Tác giả: hieult
Ngôn ngữ: C++
#include <stdio.h>
//#include <conio.h>
long long has[100001],A[100001],B[100001],KQ=0;
void kt(int n,int a[],long long x[])
{
int t=0,max,flag=0;
while(t++<n+1)
{
if(a[t]==1)
{
if(KQ<1)
KQ = 1;
flag = 1;
max = 1;
}
else if(flag!=0)
{
if(a[t]>max) max = a[t];
if(max<=t && x[t]-x[t-max]==has[max] && KQ<max)
KQ = max;
}
}
}
int main()
{
int n,a[100001],b[100001];
scanf("%d",&n);
for(int i = 1;i<=n;i++)
{
scanf("%d",&a[i]);
b[n+1-i] = a[i];
}
A[0]= 0; B[0] = 0;has[0] =0;
for(int i = 1;i<=n;i++)
{
has[i] = has[i-1]+i*i + i + 1;
A[i] = A[i-1]+a[i]*a[i] + a[i] +1;
B[i] = B[i-1]+b[i]*b[i]+b[i]+1;
}
kt(n,a,A);kt(n,b,B);
printf("%lld",KQ);
// getch();
}