Cod sursa(job #405052)

Utilizator sory1806Sandu Sorina-Gabriela sory1806 Data 27 februarie 2010 13:45:28
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.62 kb
#include<stdio.h>
#define nmax 100010
int a[nmax], best[nmax], pre[nmax], n, i, j, pmax;

void find(int i)
{	int j, ok=0;
	for(j=1; j<i; j++)
		if(best[j]+1>best[i] && a[j]<a[i])
		{	best[i]=best[j]+1; pre[i]=j; ok=1;
			if(best[i]>best[pmax])	pmax=i;
		}
	if(ok==0)	best[i]=1; 
}

int main()
{
	freopen("scmax.in", "r", stdin);
	freopen("scmax.out", "w", stdout);
	
	scanf("%d", &n);
	for(i=1; i<=n; i++)
	{	scanf("%d", &a[i]);
		find(i);
	}
	
	printf("%d\n", best[pmax]);
	i=pmax;	j=0;
	while(i!=0)
	{	j++; best[j]=a[i];
		i=pre[i];
	}
	for(; j>=1; j--)
		printf("%d ", best[j]);
	
	return 0;
	
}