Cod sursa(job #533787)

Utilizator matei_cChristescu Matei matei_c Data 14 februarie 2011 17:05:20
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.75 kb
#include<stdio.h>

int n,v[100001],lmax,x[100001],y[100001];
int who,rez[ 1000003], bla = 0;
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)
		{
			who = i;
			lmax=x[i];
		}

	printf("%d\n",lmax);
	while ( who )
	{
	//	printf("%d\n", who );
		rez[ ++bla ] = v[ who ];
		who = y[ who ];
	}
	for( i = lmax; i>= 1; i--)
		printf("%d ", rez[ i ] );
	return 0;
}