Cod sursa(job #496746)
Utilizator | Cristian Zloteanu cristian9 | Data | 30 octombrie 2010 14:27:59 |
---|---|---|---|
Problema | Subsir crescator maximal | Scor | 70 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.69 kb |
#include<stdio.h>
int v[100001], best[100001], maxt;
int main(){
freopen ("scmax.in", "r", stdin);
freopen ("scmax.out", "w", stdout);
int n, i, j;
scanf("%d ", &n);
best[n]=1;
for(i=1; i<=n; i++)
scanf("%d ", &v[i]);
for(i=n; i>=1; i--){
int max=0;
for(j=i+1; j<=n; j++){
if(v[i]<v[j])
if(best[j]>=max)
max=best[j];
}
best[i]=max+1;
if(best[i]>maxt)
maxt=best[i];
}
printf("%d\n", maxt);
for(i=1; maxt>0; i++)
if(best[i]==maxt){
printf("%d ", v[i]);
maxt--;
}
return 0;
}