Cod sursa(job #2489940)
Utilizator | Data | 9 noiembrie 2019 13:44:31 | |
---|---|---|---|
Problema | Subsir crescator maximal | Scor | 70 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva educationala | Marime | 0.67 kb |
#include <iostream>
#include <fstream>
#define Nmax 100001
using namespace std;
ifstream f("scmax.in");
ofstream o("scmax.out");
int i,j,n,dp[Nmax],v[Nmax],suc[Nmax],smax,m,imax;
int main()
{
f >> n;
for(i=1;i<=n;++i)
f >> v[i];
for(i=n;i>0;--i){
m=0;
for(j=i+1;j<=n;++j){
if(v[i]<v[j] && m<dp[j]){
m=dp[j];
suc[i]=j;
}
}
dp[i]+=m+1;
if(smax<dp[i]){
smax=dp[i];
imax=i;
}
}
o << smax << '\n';
while(imax){
o << v[imax] << " ";
imax=suc[imax];
}
return 0;
}