Cod sursa(job #721671)
#include <fstream>
using namespace std;
ifstream in("scmax.in");
ofstream out("scmax.out");
const int N=100005;
int x[N],v[N],pred[N],sol[N];
int bs(int val,int n)
{
int i,pas=1<<16;
for (i=0;pas!=0;pas>>=1)
if (i+pas<=n && v[x[i+pas]]<val)
i+=pas;
return i+1;
}
int main()
{
int n,i,nr,j,cnr;
in>>n;
for(i=1;i<=n;i++)
in>>v[i];
nr=0;
x[++nr]=1;
for(i=2;i<=n;i++)
{
j=bs(v[i],nr);
if(j>nr)
nr++;
x[j]=i;
pred[i]=j;
}
out<<nr<<"\n";
cnr=nr;
sol[nr+1]=2000000001;
for(i=n;i>=1;i--)
{
if(pred[i]==nr && v[i]<sol[nr+1])
{
sol[nr]=v[i];
nr--;
}
}
for(i=1;i<=cnr;i++)
out<<sol[i]<<" ";
out<<"\n";
return 0;
}