Cod sursa(job #808823)

Utilizator alex-rusuAlex Rusu alex-rusu Data 7 noiembrie 2012 13:42:42
Problema Subsir crescator maximal Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 0.74 kb
#include <cstdio>
using namespace std;

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



int main()
{
	FILE* f=fopen("scmax.in","r");
	FILE* g=fopen("scmax.out","w");
	
	fscanf(f,"%d",&n);
	
	for (i=0;i<n;i++)
	{
		fscanf(f,"%d",&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;
		
	fprintf(g,"%d\n%d ",maxc,v[jmax]);
	while (urm[jmax]!=-1)
	{
		fprintf(g,"%d ",v[urm[jmax]]);
		jmax=urm[jmax];
	}
	
	
	fclose(f);
	fclose(g);
	return 0;
}