Cod sursa(job #775947)

Utilizator adascaluAlexandru Dascalu adascalu Data 9 august 2012 13:20:18
Problema Subsir crescator maximal Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 0.7 kb
using namespace std;
#include<fstream>
#define Nmax 50001
#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 && max==Inf;j++)
			if(max<length[j] && v[j]>v[i])
			{
				max=length[j];
				poz[i]=j;
			}
		if(!max^Inf)
			length[i]=1;
		else
			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;
}