Cod sursa(job #454690)

Utilizator adrian_manducadrian manduc adrian_manduc Data 12 mai 2010 11:33:14
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.58 kb
#include<fstream>
using namespace std;
const int N = 1<<17;
ofstream g("scmax.out");
int lung[N],a[N],pred[N];
void scrie(int p)
{
	if(pred[p])
		scrie(pred[p]);
	g<<a[p]<<" ";
}
int main()
{
	int n,i,j,max,p,lmax=0,pmax=0;
	ifstream f("scmax.in");
	f>>n;
	for(i=1;i<=n;++i)
		f>>a[i];
	lung[1]=1;
	for(i=2;i<=n;++i)
	{
		max=0;
		p=0;
		for(j=1;j<i;++j)
			if( a[j]<a[i] && lung[j]>max)
			{
				max=lung[j];
				p=j;
			}
		lung[i]=1+max;
		pred[i]=p;
		if (lung[i]>lmax)
		{
			lmax=lung[i];
			pmax=i;
		}
	}
	g<<lmax<<"\n";
	scrie(pmax);
	return 0;
}