Cod sursa(job #427408)
Utilizator | Data | 27 martie 2010 20:42:59 | |
---|---|---|---|
Problema | Subsir crescator maximal | Scor | 70 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.54 kb |
# include <stdio.h>
# define nmax 100005
long n,a[nmax],l[nmax],p[nmax],i,j,x;
int main()
{
freopen("scmax.in","r",stdin);
freopen("scmax.out","w",stdout);
scanf("%ld", &n);
for (i=1;i<=n;i++)
scanf("%ld", &a[i]);
l[n]=1;
p[n]=-1;
for (i=n-1;i>=1;i--)
{
l[i]=1;
p[i]=-1;
for (j=i+1;j<=n;j++)
if (a[i]<a[j] && l[i]<l[j]+1)
{
l[i]=l[j]+1;
p[i]=j;
}
if (l[x]<l[i]) x=i;
}
printf("%ld\n", l[x]);
for (i=x;p[i]!=-1;i=p[i])
printf("%ld ", a[i]);
printf("%ld ", a[i]);
return 0;
}