LIS

This LIS complexity is nlog(n) & use binary search.

void LIS(long N)
{
long n=0,i,mid;

for(i=0;i<N;i++)
{
if(n==0)
{
temp[n]=sa[i];
tempP[n]=i;
A[i]=1;
n++;
}
else
{
mid = BinarySearch(0,n-1,sa[i]);

while(mid>0&&temp[mid]>sa[i])
mid–;

if(temp[mid]<sa[i])
{
A[i]=mid+2;
P[i]=tempP[mid];
if(mid+1>=n)
{
temp[n]=sa[i];
tempP[n]=i;
n++;
}
else if(temp[mid+1]>sa[i])
{
temp[mid+1]=sa[i];
tempP[mid+1]=i;
}
}
else if(temp[0]>sa[i])
{
temp[0]=sa[i];
tempP[0]=i;
}
}
}

}

void show(long h1)
{
if(P[h1]==-1)
printf(“%ld”,sa[h1]);
else
{
show(P[h1]);
printf(” %ld”,sa[h1]);
}
}

for(i=0;i<n;i++) // n number of the sequence
{
scanf(“%ld”,&sa[i]);
P[i]=-1;
}

LIS(n);

max = 0;
x = 0;

for(i=0;i<n;i++)
if(A[i]>max)
{
max = A[i];
x = i;
}

printf(“%ld\n”,max);
show(x);

Advertisements