Cod sursa(job #775951)

Utilizator adascaluAlexandru Dascalu adascalu Data 9 august 2012 13:31:39
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.65 kb
using namespace std;
#include<fstream>
#define Nmax 100001
#define Inf 0
int length[Nmax],poz[Nmax];
int main ()
{
	int i,j,n,v[Nmax],pozmax,max;
	ifstream f("scmax.in");
	f>>n;
	for(int i=1;i<=n;i++)
		f>>v[i];
	f.close();
	poz[n]=0;
	length[n]=1;
	for(i=n-1;i>=1;i--)
	{
		max=Inf;
		for(j=i+1;j<=n;j++)
			if(max<length[j] && v[j]>v[i])
			{
				max=length[j];
				poz[i]=j;
			}
		length [i]=max+1;	
	}
	max=Inf;
	for(i=1;i<=n;i++)
		if(max<length[i])
		{
			pozmax=i;
			max=length[i];
		}
	ofstream g("scmax.out");
	g<<max<<"\n";
	while(pozmax)
	{
		g<<v[pozmax]<<" ";
		pozmax=poz[pozmax];
	}
	g.close();
	return 0;
}