Cod sursa(job #699080)
| Utilizator | Data | 29 februarie 2012 17:26:34 | |
|---|---|---|---|
| Problema | Subsir crescator maximal | Scor | 0 |
| Compilator | cpp | Status | done |
| Runda | Arhiva educationala | Marime | 0.51 kb |
#include<fstream.h>
ifstream fin("scmax.in");
ofstream fout("scmax.out");
long int n,a[100001],max,im,lg[100001],u[100001],i,j,nr1;
int main()
{
fin>>n;
for(i=1;i<=n;i++)
fin>>a[i];
lg[n] = 1;
u[n] = 0;
for(i=n-1;i>=1;i--)
{
max = 0;
im = 0;
for(j=i+1; j<=n; j++)
if(a[i]<a[j] && max<lg[j])
max=lg[j], im=j;
lg[i] = max+1;
u[i] = im;
}
max=0;
for(i=1;i<=n;i++)
if(max<lg[i])
max=lg[i],im=i;
fout<<max<<'\n';
while(a[im])
{
fout<<a[im]<<' ';
im=u[im];
}
}