Cod sursa(job #415533)

Utilizator lunat1cHobinca Bogdan lunat1c Data 11 martie 2010 15:15:49
Problema Subsir 2 Scor 36
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.61 kb
// http://infoarena.ro/problema/subsir2
#include <cstdio>

int n,a[5001],b[5001];

void citire()
{
	freopen ("subsir2.in","r",stdin);
	scanf("%d", &n);
	for (int i=1;i<=n;i++)
		scanf("%d", &a[i]);
}

int main()
{
	int i,j,max,maxi;
	citire();
	b[n]=1;
	max=0;
	for (i=n-1; i>=1; i--)
	{
		for (j=i+1; j<=n; j++)
			if(a[i]<a[j] && b[i]<b[j]) b[i]=b[j];
		b[i]++;
		if(b[i]>max) max=b[i],maxi=i;
	}
	freopen ("subsir2.out","w",stdout);
	printf ("%d\n%d ", max, a[maxi]);
	i=maxi;
	for (j=1;j<=n;j++)
		if (b[j]==b[i]-1 && a[j]>a[i]) 
		{
			printf("%d ", a[j]);
			i=j;
		}
	return 0;
}