Cod sursa(job #642452)

Utilizator Cristina94Cristina Ungurean Cristina94 Data 1 decembrie 2011 13:42:51
Problema Subsir crescator maximal Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 0.62 kb
//Subsir crescator maximal
#include<stdio.h>
int x[100003], n, lis[100003], max, i, j, poz;;

int main ()
{
	freopen("scmax.in", "r", stdin);
	freopen("scmax.out", "w", stdout);
	scanf("%d", &n);
	for(i=1;i<=n;i++)
		scanf("%d", &x[i]);
	lis[n]=1;
	for(i=n-1;i>=1;i--)
	{
		max=0;
		for(j=i+1;j<=n;j++)
			if(max<=lis[i] && x[i]<x[j])
				max=lis[j];
		lis[i]=max+1;
	}
	//for(i=1;i<=n;i++) printf("%d ", lis[i]);
	max=lis[1];
	for(i=2;i<=n;i++)
		if(max<=lis[i])
			max=lis[i], poz=i;
	printf("%d\n", max);

	while(max)
		for(i=1;i<=n;i++)
			if(lis[i]==max)
				printf("%d ", x[i]), max--;
	return 0;
}