Cod sursa(job #642497)

Utilizator Cristina94Cristina Ungurean Cristina94 Data 1 decembrie 2011 15:48:59
Problema Subsir crescator maximal Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.55 kb
#include<stdio.h>
#include<iostream.h>
int main()
{
	freopen("scmax.in","r",stdin);
	freopen("scmax.out","w",stdout);
	
	int x[1000],n,i,j,lis[1000],next[1000],max, min, pozm, maxim=0;
	
	scanf("%d", &n);
	for(i=1;i<=n;i++)
		scanf("%d", &x[i]);
	lis[n]=1;
	//next[n]=n+1;
	for(i=n-1;i>=1;i--)
	{
		max=0;
		for(j=i+1;j<=n;j++)
			if(max<lis[j] && x[i]<x[j])
				max=lis[j], next[i]=j;
		lis[i]=max+1;
		if(lis[i]>maxim)
			maxim=lis[i], pozm=i;
	}
	printf("%d\n", maxim);
	for(i=pozm;i!=0;i=next[i])
		printf("%d ", x[i]);
	return 0;
}