#include<stdio.h>
#include<stdlib.h>
int lis(int *height,int n){
	int *length=(int *)malloc(sizeof(int)*n);
	int *predecessor=(int *)malloc(sizeof(int)*n);
	int *b=(int *)malloc(sizeof(int)*n);
    int i,j;
	
    /*initialization*/
	for ( i = 0; i < n; i++ ) 
		length[i] = 1, predecessor[i] = 0,b[0]=0;
    /* main algorithm*/
    for(i=0;i<n-1;i++){
		for(j=i+1;j<n;j++){
			if(height[i]<height[j]){
				if(length[i]+1>length[j]){
					length[j]=length[i]+1;
					predecessor[j]=i;
				}
			}
		}
	}
	/* lic take in b[]*/
	b[0]=height[0];
	printf("Sequence: %d ",b[0]);
	for (i=1,j=1;i<n-1;i++){
		if(length[i]!=length[i+1]){
			b[j]=height[i];
		    printf("%d ",b[j]);
			j++;
		}
	}
	b[n-1]=height[n-1];
    printf("%d \n",b[n-1]);
	printf("Max: %d\n",length[n-1]);
	/*end*/
	free( length);
	free( predecessor);
	free(b);
	return 0;
}
int main(){
    int a[]={1,6,2,3,4};
    lis(a,sizeof(a)/4);
	// Largest Increasing sequence : 1234
	//max size : 4
	return 0;
}