Cod sursa(job #533767)

Utilizator matei_cChristescu Matei matei_c Data 14 februarie 2011 16:45:35
Problema Subsir crescator maximal Scor 35
Compilator cpp Status done
Runda Arhiva educationala Marime 0.71 kb
#include<stdio.h>

int n,v[100001],lmax,x[100001],y[100001];
int main()
{
	int i,j;
	freopen("scmax.in","r",stdin);
	freopen("scmax.out","w",stdout);
	scanf("%d",&n);
	for(i=1;i<=n;i++)
		scanf("%d",&v[i]);
	lmax=1;
	x[1]=1;
	for(i=2;i<=n;i++)
	{
		x[ i ] = 1;
		y[ i ] = 0;
		for(j=i-1;j>=1;j--)
		{	
			
			if(v[i]>v[j])
			{	
				if( x[ j ] + 1 > x[ i ] )
				{
					x[ i ]= x[ j ] + 1;
					y[ i ] = j ;
				}
			}		
		}
	}	
	for(i=1;i<=n;i++)
		if(x[i]>lmax)
			lmax=x[i];
	printf("%d\n%d ",lmax,v[y[lmax]]);
	for(i=y[lmax]+1;i<=n;i++)
	{	
		if(x[i]<lmax && v[i]!=v[i-1])
			printf("%d ",v[i]);
		if(x[i]==lmax)
		{	
			printf("%d ",v[i]);
			return 0;
		}
	}	
	return 0;
}