Cod sursa(job #406229)

Utilizator laurenttlaurentiu pavel laurentt Data 1 martie 2010 12:34:51
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.74 kb
#include<stdio.h>

int a[100001], b[100001], n, c[100001], max, p;

void cit();
void rez();
void afis();

int main()
{
	freopen("scmax.in","r",stdin);
	freopen("scmax.out","w",stdout);
	
	cit();
	rez();
	afis();
	
	
	
	return 0;
}


void cit()
{
	scanf("%d",&n);
	for(int i=1; i<=n; i++)
		scanf("%d",&a[i]);
}


void rez()
{
	
	
	int i,j;
	
	b[n]=1;
	c[n]=-1;
	max=1;
	p=n;
	
	for(i=n-1; i>=1; i--)
	{
		b[i]=1;
		c[i]=-1;
		for(j=i+1; j<=n; j++)
			if(a[i]<a[j] && b[i]<b[j]+1)
			{
				b[i]=b[j]+1;
				c[i]=j;
				if(b[i]>max)
				{
					max=b[i];
					p=i;
				}
			}
	}
}
	
	
void afis()
{
	int i;
	printf("%d \n",max);
	i=p;
	while(i!=-1)
	{
		printf("%d ",a[i]);
		i=c[i];
	}
	
}