OJ Board

Code: Select all

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


int main() {
  // freopen("lis.inp","r",stdin);
    int pred[1000],i,n,j,max=0,a[1000],s=0,l[1000],dmax,j0,x[1000],k,m,sa;
    i=1;
    while(scanf("%d",&sa)!=EOF)
    {
       a[i]=sa;
       i++;
    }
    n=i-1;
    for(i=1;i<=n;i++)
        scanf("%d",&a[i]);
    l[1]=1;
    dmax=1;
    pred[1]=-1;
    pred[0]=-1;
for(i=2;i<=n;i++)
{
    max=0;
    j0=0;

    for(j=i-1;j>=1;j--)
        if(a[i]>a[j] && l[j]>max)
                {
                    max=l[j];
                    j0=j;
                }
        l[i]=max+1;
        pred[i]=j0;
        if(l[i]>=dmax) {dmax=l[i];k=i;}
}

    printf("%d\n",dmax);

       printf("-\n");


    m=0;
    while(k!=-1)
        {
            m++;
            x[m]=a[k];
            k=pred[k];
            if(k==0) break;
        }
    for(i=m;i>1;i--)
        printf("%d\n",x[i]);
        printf("%d\n",x[1]);

}