Cod sursa(job #180466)
Utilizator | Data | 17 aprilie 2008 08:35:47 | |
---|---|---|---|
Problema | Subsir crescator maximal | Scor | 70 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.52 kb |
# include <stdio.h>
long a[100000],N,i,j,m;
int main()
{
long L[100000],poz[100000];
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; poz[N]=-1;m=N;
for (i=N-1;i>0;i--){
L[i]=1; poz[i]=-1;
for (j=i+1;j<=N;j++)
if (L[i]<1+L[j] && a[i]<a[j]) {
L[i]=1+L[j];
poz[i]=j;
}
if (L[i]>L[m]) m=i;
}
printf("%ld\n",L[m]);
i=m;
while (i!=-1){
printf("%ld ",a[i]);
i=poz[i];
}
return 0;
}