Cod sursa(job #692579)

Utilizator BabutaRaresBabuta Rares Mihai BabutaRares Data 26 februarie 2012 17:20:06
Problema Subsir crescator maximal Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 0.57 kb
#include<stdio.h>
FILE *f=fopen("scmax.in","r");
FILE *g=fopen("scmax.out","w");
int main()
{
	int n,v[100001],poz[100001],max[100001],i,j,p,max1=-2100000001;
	fscanf(f,"%d",&n);
	for(i=1;i<=n;i++)
		fscanf(f,"%d",&v[i]);
	max[n]=poz[n]=0;
	for(i=n-1;i>=1;i--)
	{
		max1=0;p=0;
		for(j=i+1;j<=n;j++)
			if(v[j]>v[i]&&max[j]>=max1)
			{
				p=j;max1=max[j];
			}
		poz[i]=p;max[i]=max1+1;
	}
	max1=0;
	for(i=1;i<=n;i++)
		if(max[i]>max1)
		{
			max1=max[i];p=i;
		}
	fprintf(g,"%d\n",max1+1);
	while(p>0)
	{
		fprintf(g,"%d ",v[p]);
		p=poz[p];
	}
}