Cod sursa(job #304179)

Utilizator sorin2009Sfechis Sorin sorin2009 Data 11 aprilie 2009 11:03:28
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.76 kb

#include<fstream.h>

ifstream fin("scmax.in");
ofstream fout("scmax.out");
int main()
{
    int n,a[100001],k,j,l[100001],poz[100001],i;
    fin>>n;
    for(i=1;i<=n;i++)
    fin>>a[i];
    for(i=1;i<=n;i++) {l[i]=1;poz[i]=-1;}
    
    //****am construit vectorii l si poz
    for(k=n-1;k>=1;k--)
     for(j=n;j>k;j--)
     if(a[k]<a[j])
      if(l[j]+1>l[k])
       {l[k]=l[j]+1;
        poz[k]=j;}
       
       
//caut maximul din sirul lung
int max=0,start=0;
for(i=1;i<=n;i++)
  if (l[i]>max)
     {max=l[i];
      start=i;}
      

fout<<max<<"\n";
   //*****afisare incepand de la poz_max
   i=start;
   do
   { fout<<a[i]<<" ";
    i=poz[i];
}while (i!=-1);
             

    fin.close();
    fout.close();
    return 0;
}