Uva 497 - Strategic Defense Initiative

Problem: 497 - Strategic Defense Initiative
Description:  Longest Increasing Subsequence



Code:

/*
Algorithm: Longest Increasing Seq.
Complexity: nlgn
*/
#include<stdio.h>
#include<limits.h>
#include<string.h>
#include<stdlib.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\n",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,C=0;
    char ch[10];

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

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

    scanf("%d",&N);
    getchar();
    gets (ch);
    while(1){
       rc=1;
       i=1;
       while(gets(ch) && strlen(ch)){
           A[i] = atoi(ch);
           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];
            }
            i++;
        }
        printf("Max hits: %d\n",rc-1);
        i = Indx[rc-1];
        Print(i);
        C++;
        if(C==N) break;
        printf("\n");

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