Cod sursa(job #1282031)
| Utilizator | Data | 3 decembrie 2014 21:57:42 | |
|---|---|---|---|
| Problema | Subsir crescator maximal | Scor | 70 |
| Compilator | cpp | Status | done |
| Runda | Arhiva educationala | Marime | 0.53 kb |
#include<fstream>
#include<algorithm>
using namespace std;
ifstream cin("scmax.in");
ofstream cout("scmax.out");
int a[100005],b[100005],c[100005],i,j,n,mx,p;
int main()
{
cin>>n;
for(i=1;i<=n;++i)cin>>a[i];
b[n]=1;
c[n]=-1;
mx=1;
p=n;
for(i=n;i>=1;--i){
b[i]=1;
c[i]=-1;
for(j=i+1;j<=n;++j){
if(a[i]<a[j] && b[i]<b[j]+1){
b[i]=b[j]+1;
c[i]=j;
if(b[i]>mx)mx=b[i],p=i;
}
}
}
cout<<mx<<'\n';
i=p;
while(i!=-1){
cout<<a[i]<<' ';
i=c[i];
}
return 0;
}
