Cod sursa(job #314743)

Utilizator andrici_cezarAndrici Cezar andrici_cezar Data 12 mai 2009 20:37:48
Problema Subsir crescator maximal Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.02 kb
#include<stdio.h>   
FILE *f,*g;   
long n,a[100001],lg[100001],aux,ok,poz,aux,urm[100001],max,tt,maxm,t,j,i;
char s[10000000],q[1];
int main()
{   
f=fopen("scmax.in","rt");   
g=fopen("scmax.out","wt");   
fscanf(f,"%ld\n",&n);   
fgets(q,2,f);
fgets(s,10000000,f);
aux=0;
ok=0;
for (i=0;s[i]!='\n';++i)
    {
    if(s[i]==' '){ a[++poz]=aux;aux=0;if (ok==1) a[poz]*=-1; ok=0;}
    else if (s[i]=='-')ok=1;
               else if (s[i]!='\n'&&s[i]!=' '&&s[i]!='\x0')aux=aux*10+s[i]-'0';
    if (s[i]=='\x0') break;
    }
a[++poz]=aux;
if (ok==1) a[poz]*=-1;
lg[n]=1;
urm[n]=0;   
for (i=n-1;i>=1;i--)   
    {   
    max=0;   
    t=n;   
    for (j=n;j>i;j--)   
        if (a[i]<a[j] && lg[j]>max) {max=lg[j];t=j;}   
    lg[i]=max+1;   
    if (lg[i]>maxm) { maxm=lg[i];tt=i;}   
    urm[i]=t;   
    }   
fprintf(g,"%ld\n",maxm);   
for (i=1;i<=maxm;i++)   
    {   
    fprintf(g,"%ld ",a[tt]);   
    tt=urm[tt];   
    }   
fprintf(g,"\n");   
fclose(f);   
fclose(g);   
return 0;   
}