UVA 497 - Strategic Defense Initiative

///...................SUBHASHIS MOLLICK...................///
///.....DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING....///
///.............ISLAMIC UNIVERSITY,BANGLADESH.............///
///....................SESSION-(14-15)....................///
#include<bits/stdc++.h>
using namespace std;
#define sf(a) scanf("%lld",&a)
#define sf2(a,b) scanf("%lld %lld",&a,&b)
#define sf3(a,b,c) scanf("%lld %lld %lld",&a,&b,&c)
#define pf(a) printf("%lld",a)
#define pf2(a,b) printf("%lld %lld",a,b)
#define pf3(a,b,c) printf("%lld %lld %lld",a,b,c)
#define nl printf("\n")
#define ll long long
#define pb push_back
#define MPI map<int,int>mp;
#define fr(i,n) for(i=0;i<n;i++)
#define fr1(i,n) for(i=1;i<=n;i++)
#define frl(i,a,b) for(i=a;i<=b;i++)
//freopen("Input.txt","r",stdin);
//freopen("Output.txt","w",stdout);
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
long dp[1000],ar[1000],dir[1000];
long lisb(long u,long n)
{
    long mxx=0,v,l;
    if(dp[u]!=-1)
        return dp[u];
    for(v=u+1;v<n;v++)
    {
        if(ar[v]>ar[u])
        {
            l=lisb(v,n);
            if(l>mxx)
            {
                mxx=l;
                dir[u]=v;
            }
        }
    }
    dp[u]=mxx+1;
    return dp[u];
}
main()
{
    long ts,cs=0;
    cin>>ts;
    getchar();
    getchar();
    while(ts--)
    {
        if(cs==1)
            cout<<endl;
        cs=1;
        long k=0,i;
        string s;
        while(getline(cin,s))
        {
            if(s[0]=='\0'&&s.size()==0)
                break;
            ar[k++]=atoi(s.c_str());
        }
        memset(dp,-1,sizeof(dp));
        memset(dir,-1,sizeof(dir));
        long length,mx=0,start=0;
        for(i=0;i<k;i++)
        {
            length=lisb(i,k);
            if(length>mx)
            {
                mx=length;
                start=i;
            }
        }
        cout<<"Max hits: ";
        cout<<mx<<endl;
        cout<<ar[start]<<endl;
        while(dir[start]!=-1)
        {
            cout<<ar[dir[start]]<<endl;
            start=dir[start];
        }
    }
}