Cod sursa(job #841656)

Utilizator Brz_VladBrezae Vlad Brz_Vlad Data 24 decembrie 2012 16:13:29
Problema Subsir crescator maximal Scor 70
Compilator c Status done
Runda Arhiva educationala Marime 0.59 kb
#include <stdio.h>

#define MAXN 100000

int v[MAXN],p[MAXN],l[MAXN];
int i,j,n,pmax=0,lmax=1;


void print(int pos)
{
	if( p[pos] != -1 )
		print(p[pos]);
	printf("%d ",v[pos]);
}

int main(int argc, char* argv[])
{
	freopen("scmax.in","r",stdin);
	freopen("scmax.out","w",stdout);
	
	scanf("%d",&n);
	for(i=0;i<n;i++)
		scanf("%d",&v[i]);
	
	for(i=0;i<n;i++){
		p[i] = -1;
		l[i] = 1;
		for(j=i-1;j>=0;j--){
			if( v[i] > v[j] && (l[j]+1)>l[i] ){
				l[i] = l[j]+1;
				p[i] = j;
			}
		}
		if( l[i] > lmax ){
			lmax = l[i];
			pmax = i;
		}
	}
	
	printf("%d\n",lmax);
	print(pmax);
	
	return 0;	
}