Longest Decreasing Subsequence

Read : Longest Increasing Subsequence
Dynamic Programming:

Let Given,
A = { 0 8 4 12 2 10 6 14 1 9 5 13 3 11 7 15 }
 0 :   0
Indx: [1]
Pre:  [0]  /*Note: Parent = NULL , so it is a root node*/

 8 :    8
Indx: [2]
Pre:  [0]

4 :    8   4
Indx: [2] [3]
Pre:  .....[2]

12 :  12  4
Indx: [4] [3]
Pre:..[0]

2 :    12  4  2
Indx: [4] [3] [5]
Pre: ...........[3]

10 :  12  10  2
Indx: [4] [6] [5]
Pre: ....  [4]

 6 :   12 10 6
Indx: [4] [6] [7]
Pre: ............[6]

14 :  14 10 6
Indx: [8] [6] [7]
Pre:..[0]

 1 : 14 10 6 1
 9 : 14 10 9 1
 5 : 14 10 9 5
13 : 14 13 9 5
 3 : 14 13 9 5 3
11 : 14 13 11 5 3
 7 : 14 13 11 7 3
15 : 15 13 11 7 3

Length: 5
Seq: 12 10 9 5 3

Another Example:
 1 :   1
Indx: [1]
Pre:  [0]

 6 :   6
Indx: [2]
Pre:  [0]

 2 : 6 2
Indx: [2] [3]
Pre: ..... [2]

 3 : 6 3
Indx: [2] [4]
Pre: ....  [2]

 5 : 6 5
Indx: [2] [5]
Pre: ......[2]

Length: 2
Seq: 6 5

Code:
--------
input file:

---

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 Decreasing 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);
         /*Remove small*/
         if (R[mid]<=v){
              if (v<R[mid-1]|| v == R[mid-1])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,j;
    int rc;
    int s,e,mid;/*Binary Search*/
    int N;

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

    A[0]=R[0] = INT_MAX;
    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;
}