Longest Incresing Subsecquence(LIS) Complexity NLOG(N) + Print Path :: uva - 481

#include<stdio.h>
#include<stdlib.h>


#define max 100009


int par[max],temp[max],ind[max],n=0,data[max],l;


int lis();
void print(int i);


int main()
{
int k,x;


while(scanf("%d",&k)==1)
{
data[n++]=k;
}
if(n==0)
{
printf("1\n-\n0\n");
}
else
{
x = lis();
printf("%d\n-\n",x);
print(l);
}
return 0;
}




int comp(const void *a,const void *b)
{
int *x=(int *)a;
int *y=(int *)b;
if(*x<*y&&(y-temp==0||*x>*(y-1))) //to find LDS just change the <,> signs
return 0;
if(*x>*y)
return 1;
if(*x<*y)
return -1;
return 0;
}


int lis()
{
int i,j,*p,num,index,k;
temp[0]=data[0];
ind[0]=0;
par[0]=-1;
num=1;
//k=-1;
l=0;
for(i=1;i<n;i++)
{
p=(int*)bsearch(&data[i],temp,num,sizeof(int),comp);
if(p)
index=p-temp;
else
{
index=num;
l=i;
num++;
}
temp[index]=data[i];
ind[index]=i;
if(index==0)
par[i]=-1;
else
par[i]=ind[index-1];
}
return num;
}


void print(int i)
{
if(par[i]==-1)
{
printf("%d\n",data[i]);
return;
}
print(par[i]);
printf("%d\n",data[i]);
}


/*
Input: -7 10 9 2 3 8 8 1
Output:4 - -7 2 3 8
*/