Cod sursa(job #428992)

Utilizator veliki.velicuVelicu Stefan veliki.velicu Data 29 martie 2010 19:16:43
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.64 kb
#include<fstream>
using namespace std;
ifstream in("scmax.in");
ofstream out("scmax.out");

int v[100001], n, lung[100001], pred[100001];

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

int main()
{
	int i, j, pmaxx;
	in>>n;
	lung[1]=1;
	for(i=1; i<=n; i++)
		in>>v[i];
	for(i=2; i<=n; ++i)
	{
		lung[i]=0;
		for(j=1; j<i; ++j)
		{
			if(v[j]>=v[i])
				continue;
			if(lung[j]>lung[i])
			{
				lung[i]=lung[j];
				pred[i]=j;
			}
		}
		++lung[i];
	}
	
	pmaxx = 1;
	for(i=1; i<=n; i++)
		if(lung[i]>lung[pmaxx])
			pmaxx = i;
	out<<lung[pmaxx]<<"\n";
	sir(pmaxx);
	return 0;
}