Pagini recente » Cod sursa (job #2835438) | Cod sursa (job #3246849) | Cod sursa (job #1910934) | Cod sursa (job #2692647) | Cod sursa (job #2143142)
#include <iostream>
#include <fstream>
#include <vector>
#define inf 2000000000
using namespace std;
ifstream in("scmax.in");
ofstream out("scmax.out");
vector<long> sc;
int N;
int main()
{
in>>N;
long v[N];
for(int i=0;i<N;++i)
in>>v[i];
long dp[N],cmax=1;
for(int i=0;i<N;++i)
{
dp[i]=1;
for(int j=0;j<i;++j)
if(v[i]>v[j])
{
dp[i]=max(1+dp[j],dp[i]);
cmax=max(dp[i],cmax);
}
}
out<<cmax<<'\n';
if(1==cmax)
{
out<<v[0];
return 0;
}
int l;
for(int i=N-1;i>=0;--i)
if(cmax==dp[i])
{
l=i;
break;
}
long cont=v[l],coef=dp[l]-1;
for(int i=l-1;i>=0;--i)
{
if(v[i]<cont && dp[i]==coef)
{
sc.push_back(v[i]);
cont=v[i];
--coef;
}
if(!coef)
break;
}
while(!sc.empty())
{
out<<sc.back()<<' ';
sc.pop_back();
}
out<<v[l];
return 0;
}