Pagini recente » Cod sursa (job #630271) | Istoria paginii runda/valicaroom1/clasament | Cod sursa (job #2489593) | Cod sursa (job #1772713) | Cod sursa (job #412411)
Cod sursa(job #412411)
#include <cstdio>
#include <cstring>
#define file_in "scmax.in"
#define file_out "scmax.out"
#define Nmax 123213
int n,v[Nmax],i,j,lmax[Nmax],poz[Nmax],max,p,nr,l;
void scrie(int n, int nr)
{
if (nr>=1)
{
if (poz[n]==nr)
{
scrie(n-1,nr-1);
printf("%d ", v[n]);
}
else
scrie(n-1,nr);
}
}
int caut(int ls, int ld, int val)
{
int mij;
while(ls<=ld)
{
mij=(ls+ld)>>1;
if (lmax[mij]>=val && lmax[mij-1]<val)
return mij;
if (lmax[mij]<val)
ls=mij+1;
else
ld=mij-1;
}
return ++nr;
}
int main()
{
freopen(file_in,"r",stdin);
freopen(file_out,"w",stdout);
scanf("%d", &n);
for (i=1;i<=n;++i)
scanf("%d", &v[i]);
for (i=1;i<=n;++i)
{
l=caut(1,nr,v[i]);
lmax[l]=v[i];
poz[i]=l;
}
printf("%d\n", nr);
scrie(n,nr);
fclose(stdin);
fclose(stdout);
return 0;
}