Cod sursa(job #272806)

Utilizator vlad_olteanVladimir Oltean vlad_oltean Data 7 martie 2009 20:23:48
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.65 kb
#include <stdio.h>
#define N 100002

int v[N],p[N],s[N];
int lung[N];

int main()
{
	int max,pmax=1;
	freopen("scmax.in","r",stdin);
	freopen("scmax.out","w",stdout);
	scanf("%d",&v[0]);
	for(int i=1;i<=v[0];i++)
		scanf("%d",&v[i]);
	
	for(int i=1;i<=v[0];i++)
	{	max=lung[i];
		for(int j=1;j<i;j++)
			if(v[i]>v[j]) 
				if(max<lung[j]) 
				{	max=lung[j];
					p[i]=j;
				}
		lung[i]=max+1;
		if(lung[i]>lung[pmax])
			pmax=i;
	}
	max=lung[pmax];
	printf("%d\n",max);
	
	for(int i=pmax;i;i=p[i])
	{	s[0]++;
		s[s[0]]=i;
	}
	for(int i=s[0];i;i--)
		printf("%d ",v[s[i]]);
	
	fclose(stdin);
	fclose(stdout);
	return 0;
}