Cod sursa(job #462381)

Utilizator mihai995mihai995 mihai995 Data 10 iunie 2010 17:22:25
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.51 kb
#include <fstream>
using namespace std;

int v[1<<17],a[1<<17],p[1<<17];

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

void rec(int x)
{
	if (!x)
		return;
	rec(p[x]);
	out<<a[x]<<" ";
}

int main()
{
	int i,j,n;
	in>>n;
	for (i=1;i<=n;i++)
		in>>a[i];
	v[1]=1;
	for (i=2;i<=n;i++)
	{
		for (j=1;j<i;j++)
			if (v[i]<v[j] && a[i]>a[j])
			{
				v[i]=v[j];
				p[i]=j;
			}
		v[i]++;
	}
	for (i=j=1;i<=n;i++)
		if (v[j]<v[i])
			j=i;
	out<<v[j]<<"\n";
	rec(j);
	return 0;
}