uva - 497 - Strategic Defense Initiative

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

int list[100000],dp[100000],pre[100000],stack[100000];

int main()
{
    int T,t,i,j,top,max,final;
    char s[100],eat;
    scanf(" %d",&T);
    scanf("%c",&eat);
    gets(s);
    for(t=0;t<T;t++){
        if(t!=0)    printf("\n");
        top=max=0;
        while(gets(s)){
            if(strcmp(s,"")==0)    break;
            sscanf(s," %d",&list[top++]);
        }
        for(i=0;i<top;i++)
            dp[i]=1;
        memset(pre,-1,sizeof(pre));
        if(top>0)    max=1;
        final=top-1;
        for(i=0;i<top;i++){
            for(j=i+1;j<top;j++){
                if(list[j]>list[i]){
                    if(dp[j]<dp[i]+1){
                        dp[j]=dp[i]+1;
                        pre[j]=i;
                        if(dp[j]>=max){
                            max=dp[j];
                            final=j;
                        }
                    }
                }
            }
        }
        printf("Max hits: %d\n",max);

        if(max==0)    continue;
        int tmp=0;
        for(i=final;i!=-1;i=pre[i])
            stack[tmp++]=i;
        for(i=tmp-1;i>=0;i--)
            printf("%d\n",list[stack[i]]);
      
    }
}