Pagini recente » Cod sursa (job #1265277) | Cod sursa (job #2817321) | Cod sursa (job #2420991) | Cod sursa (job #2248181) | Cod sursa (job #2172812)
#include <iostream>
#include <fstream>
using namespace std;
ifstream in("scmax.in");
ofstream out("scmax.out");
int best[100005],pre[100005],i,j,n,v[100005];
int ULTIMATUM_L,ULTIMATUM_J;
int main()
{ int lmax,jbest;
in>>n;
for(int i=1;i<=n;++i) in>>v[i];
best[n]=1;
pre[n]=0;
for(i=n-1;i>=1;--i){
lmax=0,jbest=0;
for (int j=i+1;j<=n;++j){
if(lmax<best[j] && v[j]>v[i]){
lmax=best[j];
jbest=j;
}
if(lmax > 0) {
best[i]=lmax+1;
pre[i]=jbest;
}
else{
best[i]=1;
pre[i]=0;
}
if(best[i] > ULTIMATUM_L){
ULTIMATUM_L=best[i];
ULTIMATUM_J=i;
}
}
}
out<<ULTIMATUM_L<<'\n';
do{ out<<v[ULTIMATUM_J]<<' ';
ULTIMATUM_J=pre[ULTIMATUM_J];
}while(pre[ULTIMATUM_J] != 0);
out<<v[ULTIMATUM_J]<<'\n';
return 0;
}