Cod sursa(job #608380)

Utilizator paunmatei7FMI Paun Matei paunmatei7 Data 16 august 2011 14:50:30
Problema Subsir crescator maximal Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 0.61 kb
#include<stdio.h>
long v[100001],b[100001],max,i,n,j,r;
int main()
{
	freopen("scmax.in","r",stdin);
	freopen("scmax.out","w",stdout);
	scanf("%d",&n);
	for (i=1;i<=n;i++)
		scanf("%ld",&v[i]);
	b[n]=1;
	for (i=n-1;i>=1;i--)
	{
		max=0;
		for (j=i+1;j<=n;j++)
			if (v[i]<v[j])
			{
				if (max<b[j]+1)
					max=b[j]+1;
			}
		b[i]=max;
	}
	max=0;
	for (i=1;i<=n;i++)
		if (max<b[i])
		{
			r=i;
			max=b[i];
		}
	printf("%ld\n",max);
	max--;
	printf("%ld ",v[r]);
	while (max)
	{
		for (i=n;i>=1;i--)
			if (b[i]==max)
			{
				printf("%ld ",v[i]);
				break;
			}
		max--;
	}
}