Pagini recente » Cod sursa (job #2276860) | Cod sursa (job #1137134) | Cod sursa (job #2930148) | Cod sursa (job #2907570) | Cod sursa (job #3301944)
#include <bits/stdc++.h>
using namespace std;
int v[100055],in;
int aux[100055];
int x[100055];
vector <int> q;
int main()
{
ifstream cin("scmax.in");
ofstream cout("scmax.out");
v[0]=0;
int n;
cin>>n;
x[0]=INT_MIN;
for(int i=1;i<=n;++i)
{
cin>>x[i];
if(x[i]>x[v[in]])
{
++in;
v[in]=i;
aux[i]=v[in-1];
}
else
{
int st=1,dr=in,mij,ii=-1;
while(st<=dr)
{
mij=(st+dr)/2;
if(x[v[mij]]>=x[i])
{
dr=mij-1;
ii=mij;
}
else
{
st=mij+1;
}
}
if(ii!=-1)
{
v[ii]=i;
aux[i]=v[ii-1];
}
}
}
cout<<in<<"\n";
int nr=v[in];
while(nr!=0)
{
q.push_back(x[nr]);
nr=aux[nr];
}
for(int i=q.size()-1;i>=0;--i)
{
cout<<q[i]<<" ";
}
return 0;
}