Cod sursa(job #522194)
| Utilizator | Data | 14 ianuarie 2011 15:16:22 | |
|---|---|---|---|
| Problema | Subsir crescator maximal | Scor | 70 |
| Compilator | cpp | Status | done |
| Runda | Arhiva educationala | Marime | 0.51 kb |
#include <fstream.h>
int L[100001],t[100001],v[100001],i,j,max,p,n,k,s[100001];
ifstream f("scmax.in");
ofstream g("scmax.out");
int main (){
f >> n;
for(i=1;i<=n;i++)
f>> v[i];
L[1]=1;
for(i=2;i<=n;i++){
max=0;
p=0;
for(j=1;j<i;j++){
if(v[j]<v[i]&&L[j]>max){
max=L[j];
p=j;
}
L[i]=1+max;
t[i]=p;
}
}
for(i=1;i<=n;i++){
if(L[i]>max){
max=L[i];
j=i;
}
}
g<<max<<"\n";
i=j;
while (i){
s[++k]=v[i];
i=t[i];
}
for(;k>0;k--)
g<< s[k]<<' ';
return 0;
}
