Pagini recente » Cod sursa (job #236789) | Cod sursa (job #3205430) | Cod sursa (job #488636) | Cod sursa (job #1575094) | Cod sursa (job #2489948)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("scmax.in");
ofstream fout("scmax.out");
int DP[100005];
int x[100005];
int succ[100005];
int main()
{
int n,i,j,maxDPj = 0,sol = 0,poz = 0;
fin>>n;
for(i = 1; i <= n; i++){
fin>>x[i];
}
for(i = n; i >= 1; --i){
maxDPj = 0;
for(j = i+1; j <= n; j++){
if(x[i] < x[j]){
if(maxDPj < DP[j]){
maxDPj = DP[j];
succ[i] = j;
}
}
}
DP[i] = 1 + maxDPj;
}
for(i = 1; i <= n; i++){
if(sol < DP[i]){
sol = DP[i];
poz = i;
}
}
fout<<sol<<endl;
while(poz){
fout<<x[poz]<<" ";
poz = succ[poz];
}
return 0;
}