Cod sursa(job #993918)

Utilizator TarabanDragosTaraban Dragos-Petru TarabanDragos Data 4 septembrie 2013 18:01:33
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.95 kb
#include<cstdio>
int nmax,n,v[100001],l[2][100001],i,j,pmax,maxim,sol[100001];
FILE *f,*g;
int main(){
    f=fopen("scmax.in","r");
    g=fopen("scmax.out","w");
    fscanf(f,"%d",&n);
    fscanf(f,"%d",&v[1]);
    l[0][1]=1;
    for(i=2;i<=n;i++){
        fscanf(f,"%d",&v[i]);
        maxim=0;
        pmax=0;
        for(j=1;j<=i-1;j++){
            if(v[i]>v[j] && l[0][j]>maxim){
                maxim=l[0][j];
                pmax=j;
            }
        }
        l[0][i]=1+maxim;
        if(maxim!=0)
            l[1][i]=pmax;
    }
    nmax=0;
    for(i=1;i<=n;i++){
        if(l[0][i]>nmax){
            nmax=l[0][i];
            pmax=i;
        }
    }
    fprintf(g,"%d\n",nmax);
    i=2;
    j=pmax;
    sol[1]=v[pmax];
    while(i<=nmax){
        sol[i]=v[l[1][j]];
        j=l[1][j];
        i++;
    }
    for(i=nmax;i>=1;i--){
        fprintf(g,"%d ",sol[i]);
    }
    fclose(f);
    fclose(g);
    return 0;
}