Cod sursa(job #412411)

Utilizator AndreiDDiaconeasa Andrei AndreiD Data 5 martie 2010 16:40:25
Problema Subsir crescator maximal Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.88 kb
#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;
	
}