Cod sursa(job #309483)

Utilizator hitmannCiocas Radu hitmann Data 30 aprilie 2009 13:27:56
Problema Subsir crescator maximal Scor 10
Compilator c Status done
Runda Arhiva educationala Marime 0.71 kb
#include <stdio.h>
#include <stdlib.h>
long long v[100000],n,i,j,l[100000],t[100000],max;

int main()
{   FILE *f,*g;
    f=fopen("scmax.in","r");
    fscanf(f,"%lld",&n);
    for(i=1;i<=n;i++){ fscanf(f,"%lld",&v[i]);}
    l[n]=1;
    for(i=n-1;i>0;i--){
        t[i]=0;
     for(j=i+1;j<=n;j++)
      if((v[i]<v[j])&&(l[i]<=l[j]+1))
           {
             t[i]=j;
             l[i]=l[j]+1;
           }
    }
      max=0;
      j=0;
    for(i=1;i<=n;i++) if(max<l[i]) { max=l[i]; j=i; }
   g=fopen("scmax.out","w");
   fprintf(g,"%lld\n",max);
    while (j)
         {
             fprintf(g,"%lld ",v[j]);
             j=t[j];
         }
   fclose(f);
   fclose(g);

 return 0;
    }