Cod sursa(job #661240)

Utilizator stanescu_teodorStanescu Teodor stanescu_teodor Data 14 ianuarie 2012 05:56:57
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.6 kb
#include <fstream>

using namespace std;

int s[100001],a[100001],poz[100001],i,j,pozmax,n,maxim;

int main ()
{
	ifstream f ("scmax.in");
	ofstream g ("scmax.out");
	f >> n;
	for (i=1; i<=n; i++)
		f>>s[i];
	a[n]=1; 
	poz[n]=-1; 
	maxim=1; 
	pozmax=n;
	for(i=n-1; i>0; i--)
	{   
		a[i]=1;
		poz[i]=-1;
		for (j=i+1; j<=n; j++)
			if (s[i]<s[j] && a[i]<a[j]+1)
			{   
				a[i]=a[j]+1;
				poz[i]=j;
				if (a[i]>maxim)
				{
					maxim=a[i];
					pozmax=i;
				}
			}
	}
	g << maxim << endl;
	while (pozmax!=-1)
	{   
		g<<s[pozmax]<<' ';
		pozmax=poz[pozmax];
	}
return 0;
}