Pagini recente » Cod sursa (job #2751332) | Cod sursa (job #2974036) | Cod sursa (job #2974039) | Cod sursa (job #2975372) | Cod sursa (job #3314125)
#include <fstream>
#include <vector>
using namespace std;
ifstream cin("scmax.in");
ofstream cout("scmax.out");
int v[100005];
int f[100005];
int tr[100005];
vector <int> rez;
int main()
{
int n, mx=0, cj;
cin>>n;
for(int i=1; i<=n; i++)
{
cin>>v[i];
}
for(int i=1; i<=n; i++)
{
cj=mx=0;
for(int j=i-1; j>=0; j--)
{
if(v[j]<v[i])
{
if(mx<f[j])
{
mx=f[j];
cj=j;
}
}
}
if(mx+1>=f[i-1])
{
tr[i]=cj;
f[i]=mx+1;
}
else
{
f[i]=f[i-1];
tr[i]=tr[i-1];
}
}
cout<<f[n]<<'\n';
int poz=n;
while(poz>0)
{
rez.push_back(v[poz]);
poz=tr[poz];
}
for(int i=rez.size()-1; i>=0; i--)
{
cout<<rez[i]<<" ";
}
return 0;
}