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

// Returns the length of the longest increasing subsequence.
// Note that this is looking for the longest strictly increasing subsequence.  
//    This can be easily modified for other situations.

int lcs( int* a, int N ) {
   int *best, *prev, i, j, max = 0;
   int last;
   int o[10],c1;
   best = (int*) malloc ( sizeof( int ) * N );
   prev = (int*) malloc ( sizeof( int ) * N );
 
   for ( i = 0; i < N; i++ ) best[i] = 1, prev[i] = -1;
 
   for ( i = 1; i < N; i++ )
      for ( j = 0; j < i; j++ )
         if ( a[i] > a[j] && best[i] < best[j] + 1 )
            best[i] = best[j] + 1, prev[i] = j;  // prev[] is for backtracking the subsequence
   
   for ( i = 0; i < N; i++ ){
	   if ( max < best[i] ){
            max = best[i];
			last=i;
	   }
			
   }
   
   c1=0;
   printf("max: %d,last: %d \n",max,last); 
   for(i=0;i<N;i++)
	   printf("%d ",prev[i]);
   printf("\n");
   while(1){
	   if(last==-1){
	     //printf("%d",a[last]);
		 break;
	   }
	   else{
          printf("%d",a[last]);
		  o[c1]=a[last];
		  c1++;
	      last=prev[last];

	   }
   }
   printf("\n");
   for(i=c1-1;i>=0;i--)
	   printf("%d ",o[i]);
   printf("\n");



   free( best );
   free( prev );
 
   return max;
}
 
// Sample usage.
int main(){
  int b[] = { 1, 3, 2, 4, 3, 5, 4, 6 };
  // the longest increasing subsequence = 13456?
  // the length would be 5, as well lcs(b,8) will return.
  printf("max: %d\n", lcs( b, 8 ) );
}