Cod sursa(job #415552)

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

int n,a[5001],b[5001],poz[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], poz[i]=j;
			else
				if (a[i]<=a[j] && b[i]==b[j]) poz[i]=j;					
		b[i]++;
		if(b[i]>max) max=b[i],maxi=i;
	}
	freopen ("subsir2.out","w",stdout);
	printf ("%d\n", max, a[maxi]);
	i=maxi;
	for(j=1;j<=max;j++)
	{
		printf("%d ", a[i]);
		i=poz[i];
	}
	return 0;
}