Cod sursa(job #693869)

Utilizator lucian666Vasilut Lucian lucian666 Data 27 februarie 2012 17:27:59
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.71 kb
#include<fstream>
using namespace std;
#define NN 100001
ofstream out("scmax.out");
int v[NN],l[NN],poz[NN],n;
void citire();
void dinamica();
void afis();
int main()
{
	citire();
	dinamica();
	afis();
	return 0;
}
void citire()
{
	ifstream in("scmax.in");
	in>>n;
	for(int i=1;i<=n;i++)
		in>>v[i];
}
void dinamica()
{
	int i,j,k;
	l[n]=1;
	poz[n]=-1;
	for(i=n-1;i>=1;i--)
	{
		l[i]=1;
		poz[i]=-1;
			for(j=i+1;j<=n;j++)
				if(v[i]<v[j])
					if(l[i]<l[j]+1)
					{
						l[i]=1+l[j];
						poz[i]=j;
					}
	}
}
void afis()
{
	int i,j,start=1;
	for(i=1;i<=n;i++)
		if(l[start]<l[i])
			start=i;
		out<<l[start]<<'\n';
		for(i=start;i!=-1;i=poz[i])
			out<<v[i]<<" ";
}