Longest Increasing Subsequence

The longest increasing subsequence problem is to find a subsequence of a given sequence in which the subsequence's elements are in sorted order, lowest to highest, and in which the subsequence is as long as possible. he longest increasing subsequence problem is solvable in time O(n log n), where n denotes the length of the input sequence.
Example:
In the first 16 terms of the binary Van der Corput sequence

0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15

a longest increasing subsequence is

0, 2, 6, 9, 11, 15.

This subsequence has length six; the input sequence has no seven-member increasing subsequences. The longest increasing subsequence in this example is not unique: for instance,

0, 4, 6, 9, 11, 15 or 0, 4, 6, 9, 13, 15

are other increasing sub sequences of equal length in the same input sequence [Wiki].
Dynamic Problem:

Explain the procedure to find LIS (Complexity: O(nlgn):
We maintain three array variable , R[], Indx[] and Pre[]
rc = 1;
[1] Take ith element int v, if v > R[rc-1] then R[rc] = v,Indx[rc] =i,Pre[i] =Indx[rc-1]
[2] if v (Use Binary Search)
[3] R[Pos] = v, Indx[Pos] = i, Pre[i] = Indx[Pos-1]

A = {-7 10 9 2 3 8 8 1} [Let index start from 1]
R[0] = INT_MIN, Indx [0] = 0

v=-7, R = {-7} ( because v>R[0] ) Indx = {1}, Pre = {0} root
v = 10, R ={-7 10} , Indx = {1,2}, Pre = {0,1};
v = 9 , R = {-7 9} , Indx = {1, 3} , Pre = {0,1,1}
v = 2, R = {-7 2}, Indx = {1,4}, Pre= {0,1,1,1}
v = 3, R = {-7 2 3}, Indx = {1,4,5}, Pre= {0,1,1,1,4}
v = 8, R = {-7 2 3 8}, Indx = {1,4,5,6}, Pre= {0,1,1,1,4,5}
v= 8, R = {-7 2 3 8}, Indx = {1,4,5,6}, Pre= {0,1,1,1,4,5,0}
v = 1, R = {-7 1 3 8}, Indx = {1,8,5,6}, Pre= {0,1,1,1,4,5,5,0,1}

More Clear:
index:  [1]  [2]  [3] [4] [5] [6] [7] [8]
A     :  -7  10   9   2   3   8   8  1
Pre : [0]
Indx: [1]
-7 :  -7

Pre : [0]  [1]
Indx: [1]  [2]
10:    -7 10

Pre : [0] [1]
Indx: [1] [3]

9 :    -7  9

Pre : [0] [1]
Indx: [1] [4]
2 :    -7  2

Pre : [0] [1] [4]
Indx: [1] [4] [5]

3 :    -7   2 3

Pre : [0] [1] [4] [5]
Indx: [1] [4] [5] [6]

8 :    -7  2   3  8

Pre : [0] [1] [4] [5]
Indx: [1] [4] [5] [6]
8 :     -7 2   3   8

Pre : [0] [1] [4] [5]
Indx: [1] [8] [5] [6]
1 :    -7  1   3  8
Print: A[Indx[4] =6] - > A[Pre[6]=5] - > A[Pre[5] =4] - > A[Pre[4] =1] - > Pre[1]=0 break
8 3 2 -7 - > -7 2 3 8
input file: LIS.in

---

16
0 8 4 12 2 10 6 14 1 9 5 13 3 11 7 15
8
-7 10 9 2 3 8 8 1
5
1 6 2 3 5
0

---

/*
Algorithm: Longest Increasing Seq.
Complexity: nlgn
*/
#include<stdio.h>
#include<limits.h>
#define S 100000

int R[S]={0};/*Generated Table*/
int A[S] = {0};/*Input data*/
int Indx[S]= {0}; /*Index of the Table Element*/
int Pre[S]={0}; /*Previous Element*/

void Print(int i){
    if ( i == 0) return;
    else {
        Print(Pre[i]);
        printf("%d ",A[i]);
    }
    return;
}
/*Complexity lg2^N*/
int BS(int v,int s,int e){
    int mid=0;
    while(s<=e){
         mid = s+((e-s)/2);
         if (v<=R[mid]){
              if(R[mid-1]<v) break;
              e = mid-1;
         }
         else if (v>R[mid]){
            if(R[mid+1]>=v){mid= mid+1;break;}
            s = mid+1;
         }
    }
    return mid;
}

int main(){
    int i,v=0;
    int rc;
    int s,e,mid;/*Binary Search*/
    int N;

    freopen("LIS.in","r",stdin);

    A[0]=R[0] = INT_MIN;
    Indx[0] = 0;

    while(1){
       scanf("%d",&N);
       if(N==0) break;

       rc=1;
       for(i=1;i<=N;i++){
           scanf("%d",&A[i]);
           v = A[i];
           if(v>R[rc-1]){
              R[rc] = v;
              Indx[rc] = i;
              Pre[i] = Indx[rc-1];
              rc++;
           }
           else if(v<R[rc-1]){/*Binary Search*/
              mid = BS(v,1,rc-1);
              R[mid] = v;
              Indx[mid]= i;
              Pre[i] = Indx[mid-1];
            }
        }
        printf("Length: %d\n",rc-1);
        printf("Seq: ");
        i = Indx[rc-1];
        Print(i);
        printf("\n\n");

        for(i=1;i<=N;i++) Pre[i]=0,Indx[i]=0,R[i]=0;
    }
    return 0;
}

Explain the procedure to find LIS (Complexity: O(n^2):

A : Given Data set
Pre : Predecessor of a number
L  : Length of the seq save
max: Max length
End: End Element index
Let Index start from 1
A = {1 6 2 3 5}  N = 5
i : = 1 , j : = 2 to 5
A[2:5]={6 2 3 5} >A[i] and L[i]+1 > L[j]
i.e. L[1]+1 = 2> L[2] =1 , L[1] = 2, Pre[2] = i =1, max=2, End = 2
L[1]+1 = 2> L[3] =1 , L[3] = 2 , Pre[3] = i =1
L[1]+1 = 2> L[4] =1 , L[4] = 2, Pre[4] = i =1
L[1]+1 = 2> L[5] =1 , L[5] = 2, Pre[5] = i =1
L: [ 1 2 2 2 2 ]
Pre: [ 0 1 1 1 1 ]
max = 2, End = 5

i = 2, j: 3 to 5
A[3:5] = {2 3 5} < A[i] and L[i]+1 > L[j] ------ > false

L: [ 1 2 2 2 2 ]
Pre: [ 0 1 1 1 1 ]

max = 2, End = 5

i = 3, j: 4 to 5
A[3:5] = {3 5}  >  A[i] and L[i]+1 > L[j] 

L: [ 1 2 2 3 3 ]
Pre: [ 0 1 1 3 3 ]
max = 3, End= 5

i = 4, j: 5 to 5
A[3:5] = {5} >  A[i] and L[i]+1 > L[j] 
L: [ 1 2 2 3 4 ]
Pre: [ 0 1 1 3 4 ]
max = 4, End=5

Given Sq: 1 6 2 3 5
Length: 4
Sq: 1 2 3 5

			j = i+1
			1	6	2	3	5	Check Increasing Value and path Any Node to j and I to j Compare
		L	1	1	1	1	1
		Pre	0	0	0	0	0
i= 1 to N-1	1	L		2	2	2	2
		Pre		1	1	1	1
	6	L			2	2	2
		Pre			1	1	1
	2	L				3	3
		Pre				3	3
	3	L					4
		Pre					4
	5

Pre = {0 1 1 3 4}
End = 5 Print - > A[5] - > A [Pre[5] = 4] - > A [Pre [4] = 3] - > A[ Pre[3] = 1] - > A[Pre[1] =0]  Break
Max = Max (L) = 4

Another:
A = {-7 10 9 2 3 8 8}

L: [ 1 2 2 2 2 2 2 ]
Pre: [ 0 1 1 1 1 1 1 ]
Max = 2 End : 7

L: [ 1 2 2 2 2 2 2 ]
Pre: [ 0 1 1 1 1 1 1 ]
Max = 2 End : 7

L: [ 1 2 2 2 2 2 2 ]
Pre: [ 0 1 1 1 1 1 1 ]
Max = 2 End : 7

L: [ 1 2 2 2 3 3 3 ]
Pre: [ 0 1 1 1 4 4 4 ]
Max = 3 End : 7

L: [ 1 2 2 2 3 4 4 ]
Pre: [ 0 1 1 1 4 5 5 ]
Max = 4 End : 7

L: [ 1 2 2 2 3 4 4 ]
Pre: [ 0 1 1 1 4 5 5 ]
Max = 4 End : 7

Given Sq: -7 10 9 2 3 8 8
Length: 4
Sq: -7 2 3 8

			j = i+1
			-7	10	9	2	3	8	8	Check Increasing Value and path Any Node to j and I to j Compare
		L	1	1	1	1	1	1	1
		Pre	0	0	0	0	0	0	0
i= 1 to N-1	-7	L		2	2	2	2	2	2
		Pre		1	1	1	1	1	1
	10	L			2	2	2	2	2
		Pre			1	1	1	1	1
	9	L				2	2	2	2
		Pre				1	1	1	1
	2	L					3	3	3
		Pre					4	4	4
	3	L						4	4
		Pre						5	5
	8	L							4
		Pre							5
	8

Pre = { 0 1 1 1 4 5 5}
End = 6 ( Last change Occur);
A[End = 6] - > A[ Pre [End] = 5] - > A[Pre[5] = 4]  - > A[Pre[4]=1] - > A[Pre [1] = 0]
8 3 2 -7 ==> -7 2 3 8

Max = Max(L) = 4

Code:
------

/*Algorithm: LIS
Complexity: O(n^2)
*/
/*
Algorithm: LIS
Complexity: O(n^2)
A [] : Given Data set
Pre [] : Predecessor of a number
L [] : Length of the seq save
max: Max length
End: End Element index
*/
#include <limits.h>
#include<stdlib.h>
#include<stdio.h>
#define S 10000

void print(int *A, int *Pre,int End){
  if ( End == 0) return;
  else{
      print(A,Pre,Pre[End]);
      printf("%d ",A[End]);
  }
  return;
}

int main(){
  int A[S];
  int N = 16;
  int Pre[S],L[S];
  int i,j,max,End;

  freopen("LIS.in","r",stdin);

  while(1){
    scanf("%d",&N);
    if (N==0) break;
    for ( i = 1; i<=N ; i++) scanf("%d",&A[i]);


    /*Algorithm start: O(n^2)*/
    max = INT_MIN;
    End = 0;
    for ( i = 1; i<=N ; i++) Pre[i]=0,L[i]=1;;
    for (i = 1; i <= (N-1); i++){
      for (j = i+1; j <= N; j++){
          if ( A[j]> A[i] && L[i]+1>L[j]){
            Pre[j] = i;
            L[j] = L[i]+1;
            End = j;
            max = L[j];
          }
      }
    }

    /*Print*/
    printf("Given Sq: ");
    for(i=1;i<=N;i++) printf("%d ",A[i]);
    printf("\n");
    printf("Length: %d\n",max);
    printf("Sq: ");
    print(A,Pre,End);
    printf("\n\n\n");
  }
  return 0;
}

Output:

Given Sq: 0 8 4 12 2 10 6 14 1 9 5 13 3 11 7 15
Length: 6
Sq: 0 4 6 9 13 15


Given Sq: -7 10 9 2 3 8 8 1
Length: 4
Sq: -7 2 3 8


Given Sq: 1 6 2 3 5
Length: 4
Sq: 1 2 3 5



Process returned 0 (0x0)   execution time : 0.797 s
Press any key to continue.