Cod sursa(job #349288)
| Utilizator | Data | 18 septembrie 2009 22:24:53 | |
|---|---|---|---|
| Problema | Subsir crescator maximal | Scor | 70 |
| Compilator | cpp | Status | done |
| Runda | Arhiva educationala | Marime | 0.57 kb |
#include<stdio.h>
#define nmax 100009
int n, a[nmax],i,j, next[nmax], length[nmax],max=0,p;
int main()
{
freopen("scmax.in", "r", stdin);
freopen("scmax.out", "w", stdout);
scanf("%d", &n);
for(i=1;i<=n;i++)
scanf("%d", &a[i]);
for(i=n-1;i>=1;i--)
for(j=i+1;j<=n;j++)
if(a[i]<a[j]&&length[j]>=length[i])
{
next[i]=j;
length[i]=length[j]+1;
if(length[i]>max)
{
max=length[i];
p=i;
}
}
printf("%d\n", max+1);
for(i=1;i<=max+1;i++)
{
printf("%d ", a[p]);
p=next[p];
}
return 0;
}
