Cod sursa(job #522419)

Utilizator balakraz94abcd efgh balakraz94 Data 15 ianuarie 2011 09:33:34
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.77 kb
#include<cstdio>
#include<algorithm>
using namespace std;
#define l 100001

int Lg[l],urm[l];
int a[l];
int n;

void citire();

void citire()
{
	freopen("scmax.in","r",stdin);
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	
	fclose(stdin);
}

int main()
{
	int i,j,max,im;
	citire();
	Lg[n]=1;
	urm[n]=0;
	for(i=n-1;i>0;i--) 
	{
		max=im=0;
		for( j=i+1;j<=n;j++)
			if(a[i]<a[j] && max<Lg[j])
			{
				max=Lg[j];
				im=j;
			}
			Lg[i]=max+1;
			urm[i]=im;
	}
	
	max=Lg[1];
	im=1;
	for(i=2;i<=n;i++) 
		if(max<Lg[i])
		{
			max=Lg[i];
			im=i;
		}
		
		freopen("scmax.out","w",stdout);
		
		printf("%d\n",max);
		do
		{
			printf("%d ",a[im]);
			im=urm[im];
		}while(im);
		printf("\n");
        fclose(stdout);
}