Cod sursa(job #255848)

Utilizator irene_mFMI Irina Iancu irene_m Data 10 februarie 2009 19:40:58
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.65 kb
#include <fstream.h>
unsigned long a[100000];
int n,l[100000],j,i,p,max=0;

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

int main()
{
	cit();
	l[n]=1;
	for(i=n-1;i>=1;i--)
	{
		max=0;
		for(j=i+1;j<=n;j++)
			if(a[j]>a[i] && l[j]>max)
				max=l[j];
		l[i]=max+1;
	}
	
	max=0; p=0;
	for(i=1;i<=n;i++)
		if(l[i]>max)
		{
			max=l[i];
			p=i;
		}
	
	ofstream fout("scmax.out");
	fout<<max<<'\n';
	
	while(max>0)
	{
		fout<<a[p]<<" ";
		max--;
		for(i=p+1;i<=n;i++)
			if(l[i]==max && a[i]>a[p])
			{
				p=i;
				i=n+1;
			}
	}
	
	fout.close();
	return 0;
}