Cod sursa(job #905570)

Utilizator dariusgDarius Galis dariusg Data 5 martie 2013 22:16:21
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.81 kb
#include <cstdio>
FILE *f=fopen("scmax.in","r");
FILE *g=fopen("scmax.out","w");
int v[100000],lung[100000],poz[100000];
int n,i,j,max,p;


int main()
{
    fscanf(f,"%d",&n);
    for(i=1;i<=n;i++)
        fscanf(f,"%d",&v[i]);
    
    max=1;
    lung[n]=1;
    for(i=n-1;i>=1;i--)
    {
        lung[i]=1;
        for(j=i+1;j<=n;j++)
            if(v[i]<v[j])//crescator
                if(lung[i]<lung[j]+1)
                {
                    lung[i]=lung[j]+1;
                    poz[i]=j;
                }
        
        if(lung[i]>max)
        {
            max=lung[i];
            p=i;
        }
    }
    fprintf(g,"%d\n%d ",max,v[p]);
    for(i=1;i<max;i++)
    {
        p=poz[p];
        fprintf(g,"%d ",v[p]);
    }
    
    fclose(f);
    fclose(g);
    return 0;
}