Pagini recente » Cod sursa (job #2287316) | Cod sursa (job #1063400) | Cod sursa (job #1285570) | Cod sursa (job #2655385) | Cod sursa (job #3203020)
//https://www.infoarena.ro/problema/scmax
#include <bits/stdc++.h>
using namespace std;
ifstream fin("scmax.in");
ofstream fout("scmax.out");
int v[100010],d[100010],ret[100010];//100010
int main()
{
int n,i,j;
fin>>n;
for(i=1;i<=n;i++)
{
fin>>v[i];
}
d[0]=0;
d[1]=1;
int max=0,maxi=0;
for(i=2;i<=n;i++)
{
int val=0;
for(j=1;j<i;j++)
{
if(v[j]<v[i]&&d[j]>val)
{
val=d[j];
ret[i]=j;
}
}
d[i]=d[ret[i]]+1;
if(d[i]>max)
{
max=d[i];
maxi=i;
}
}
fout<<max<<"\n";
vector <int> ve;
i=maxi;
while(i!=ret[i])
{
ve.push_back(v[i]);
//cout<<v[i]<<" ";
i=ret[i];
}
for(i=ve.size()-1;i>=0;i--)
{
fout<<ve[i]<<" ";
}
return 0;
}