Cod sursa(job #689474)

Utilizator noruIlies Norbert noru Data 24 februarie 2012 15:45:16
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.53 kb
#include<fstream>
using namespace std;
int main()
{
	ifstream f("scmax.in");
	ofstream g("scmax.out");
	int v[100001],poz[100001],l[100001],i,j,p,max,n;
	f>>n;
	for (i=1;i<=n;i++) l[i]=1;
	for (i=1;i<=n;i++)
		f>>v[i];
	for (i=n-1;i>=1;i--)
	{
		max=p=0;
		for (j=i+1;j<=n;j++)
			if (v[i]<v[j]&&l[j]>=max)
			{
				max=l[j];
				p=j;
			}
		l[i]=max+1;
		poz[i]=p;
	}
	max=p=0;
	for (i=1;i<=n;i++)
		if (max<l[i]){ max=l[i];p=i;}
	g<<max<<'\n';
	while (p>0)
	{
		g<<v[p]<<' ';
		p=poz[p];
	}
	return 0;
}