Cod sursa(job #357464)

Utilizator unknownliviuMaria Liviu Valentin unknownliviu Data 19 octombrie 2009 13:11:38
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.71 kb
#include<fstream>
using namespace std;

ifstream in("scmax.in");
ofstream out("scmax.out");

int lung[100000],pred[100000];
int i,n,v[100000];
int lgmax;

void lag(int y)
{
	int max=0,maxj=0;
	for(int j=1;j<y;j++)
		if(v[j]<v[y] && lung[j]>max)
		{
			max=lung[j];
			maxj=j;
		}
	if(!max)
		lung[y]=1;
	else
	{
		lung[y]=lung[maxj]+1;
		pred[y]=maxj;
	}
}

void lg()
{
	
	for(i=1;i<=n;i++)
		if(lung[i]>lung[lgmax])
			lgmax=i;
}

void print(int poz)
{
	if(pred[poz])
		print(pred[poz]);
	out<<v[poz]<<" ";
}

void afisare()
{
	out<<lung[lgmax]<<"\n";
	print(lgmax);
}

int main()
{
	in>>n;
	for(i=1;i<=n;i++)
	{	
		in>>v[i];
		lag(i);
	}
	lg();
	afisare();
	exit(0);
}