Cod sursa(job #202768)

Utilizator Astrid28Ruxandra Cohal Astrid28 Data 11 august 2008 11:33:25
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.96 kb
#include<fstream.h>
#include<string.h>
#define MAX 1000001

long n, a[MAX];
ofstream fout("scmax.out");


void citire()
{
	int i;
	ifstream fin("scmax.in");
	fin>>n;
	for(i=1;i<=n;i++)
		fin>>a[i];
	fin.close();
}



void lungime_max(long l[MAX], long &lmax, long &poz)
{
	 long i;
	 lmax=l[1]; poz=1;
	 for(i=2;i<=n;i++)
		 if(l[i]>lmax)
			 lmax=l[i], poz=i;
}



void sc(long poz, long pred[MAX], long l[MAX])
{
	if (pred[poz]!=0)
		{
			sc(pred[poz], pred, l);
			fout<<a[poz]<<' ';
		}
	 else fout<<a[poz]<<' ';
}



void det()
{
	long l[MAX], pred[MAX],i,j,lmax,poz;
	memset(l, 0, sizeof(l));
	memset(pred, 0, sizeof(pred));
	l[1]=1;
	for(i=2;i<=n;i++)
		{
			for(j=1;j<i;j++)
				if(a[i]>a[j] && l[j]+1>l[i])
					l[i]=l[j]+1, pred[i]=j;
			if (l[i]==0) l[i]++;
		}

	lungime_max(l,lmax,poz);
	fout<<lmax<<'\n';
	sc(poz,pred,l);
	fout<<'\n';
	fout.close();
}


int main()
{
	citire();
	det();
	return 0;
}