Cod sursa(job #720197)

Utilizator raulstoinStoin Raul raulstoin Data 22 martie 2012 14:00:46
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.7 kb
#include<fstream>
using namespace std;
int a[100000],c[100000],n,poz_max,lung_max;

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