Cod sursa(job #174988)

Utilizator anamaria1Ozorchevici Ana Maria anamaria1 Data 9 aprilie 2008 14:07:18
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.55 kb
#include<fstream.h>
#define dim 100001
unsigned long v[dim],l[dim],par[dim];
int main()
{ifstream f("scmax.in");
ofstream g("scmax.out");
unsigned long n,max,imax,i,j;
f>>n;
for(i=1;i<=n;++i) f>>v[i];
f.close();
l[n]=1;par[n]=0;
for(i=n-1;i>=1;i--)
 {max=imax=0;
  for(j=i+1;j<=n;++j)
   if((max<l[j])&&(v[i]<v[j]))
     max=l[j],imax=j;
  l[i]=max+1;par[i]=imax;
 }
max=l[1];imax=1;
for(i=2;i<=n;++i)
 if(l[i]>max) max=l[i],imax=i;
g<<max<<'\n';
do
 {g<<v[imax]<<" ";
  imax=par[imax];
 }
while(imax);
g<<'\n';
g.close();
return 0;
}