Cod sursa(job #349288)

Utilizator borsoszalanBorsos Zalan borsoszalan Data 18 septembrie 2009 22:24:53
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.57 kb
#include<stdio.h>
#define nmax 100009

int n, a[nmax],i,j, next[nmax], length[nmax],max=0,p;

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]);
	for(i=n-1;i>=1;i--)
		for(j=i+1;j<=n;j++)
			if(a[i]<a[j]&&length[j]>=length[i])
			{
				next[i]=j;
				length[i]=length[j]+1;
				if(length[i]>max)
				{
					max=length[i];
					p=i;
				}
				
			}
	printf("%d\n", max+1);
	for(i=1;i<=max+1;i++)
		{
			printf("%d ", a[p]);
			p=next[p];
	}
	return 0;
}