Pagini recente » Cod sursa (job #562245) | Cod sursa (job #373472) | Cod sursa (job #67659) | Cod sursa (job #53067) | Cod sursa (job #1866165)
#include<cstdio>
using namespace std;
const int nmax=100005;
int q[nmax],p[nmax],sol[nmax],v[nmax],n,l=0,lmax=0;
int cautbin(int x)
{
int st,dr,med;
st=1;
dr=l;
while(st<=dr)
{
med=(st+dr)/2;
if(q[med]<x)
st=med+1;
else
dr=med-1;
}
if(q[st-1]==x&&st>l)
return st-1;
return st;
}
void aplica(int x,int a)
{
int i;
if(!l)
{
q[++l]=x;
p[l]=1;
}
else if(l==1)
{
if(q[1]>x)
{
q[1]=x;
p[a]=1;
}
else if(q[1]<=x)
{
q[++l]=x;
p[a]=2;
}
}
else
{
i=cautbin(x);
if(i>l)
l=i;
q[i]=x;
p[a]=i;
}
return;
}
int main()
{
freopen("scmax.in","r",stdin);
freopen("scmax.out","w",stdout);
int i;
scanf("%d",&n);
for(i=1;i<=n;i++)
{
scanf("%d",&v[i]);
aplica(v[i],i);
}
printf("%d\n",l);
lmax=l;
for(i=n;i>=0;i--)
{
if(p[i]==lmax)
{
sol[lmax]=v[i];
lmax--;
}
}
for(i=1;i<=l;i++)
printf("%d ",sol[i]);
}