Cod sursa(job #808807)

Utilizator alex-rusuAlex Rusu alex-rusu Data 7 noiembrie 2012 13:32:55
Problema Subsir crescator maximal Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.68 kb
#include <fstream>
using namespace std;

int v[100000],i,n,lgmax[100000],maxc,j,urm[100000],jmax;



int main()
{
	ifstream f("sir.in");
	ofstream g("sir.out");
	
	f>>n;
	
	for (i=0;i<n;i++)
	{
		f>>v[i];
	}
	lgmax[n-1]=1;
	for (i=n-2;i>=0;i--)
	{
		maxc=1;
		jmax=-1;
		for (j=1;j+i<=n-1;j++)
		{
			if (v[i]<v[j+i])
			{
				if (maxc<=lgmax[j+i]+1)
					maxc=lgmax[j+i]+1,jmax=j+i;
			}
		}
		lgmax[i]=maxc;
		urm[i]=jmax;
	}
	maxc=0;
	
	for (i=0;i<n;i++)
		if (maxc<=lgmax[i])
			maxc=lgmax[i],jmax=i;
	g<<maxc<<'\n'<<v[jmax]<<' ';	
	while (urm[jmax]!=-1)
	{
		g<<v[urm[jmax]]<<' ';
		jmax=urm[jmax];
	}
	
	
	f.close();
	g.close();
	return 0;
}