Cod sursa(job #386140)

Utilizator pirvupirvu tudor pirvu Data 24 ianuarie 2010 10:44:10
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.88 kb
/*
a[] = vectorul principal 

v[] --> v[i] in ce subsir e elementul a[i]

h[] --> h[i] Ultimul element din subsirul I .. Cel mai mic 

lung[i] --> lungimea celui mai lung subsir care se termina cu a[i]
*/

#include<cstdio>

int a[100001];
int lung[100001];
int pred[100001];
int n;
int max,maxi;

void scrie(int i)
{
	if (i==0) return ;
	scrie (pred[i]);
	printf("%d ", a[i]);
	
}

int main()
{
	
	freopen("scmax.in","r",stdin);
	freopen("scmax.out","w",stdout);
	
	scanf("%d", &n);
	
	for (int i=1;i<=n;i++)
		scanf("%d", &a[i]);
	
	lung[1]=1;
	
	for ( int i=2;i<=n;i++)
	{
		lung[i]=0;
		for (int j=1;j<i;j++)
			if (lung[j]>lung[i])
				if (a[j]<a[i])
				{
					lung[i]=lung[j];
					pred[i]=j;
				}
		lung[i]++;
		if (lung[i]>max)
		{
			max=lung[i];
			maxi=i;
		}
	}
	
	printf("%d\n", max);
	
	scrie (maxi);
	
	
	return 0;
}