Cod sursa(job #360340)

Utilizator alexsobiMardare Alexandru Gabriel alexsobi Data 31 octombrie 2009 09:58:55
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.63 kb
#include<fstream>

using namespace std;

int a[100001],lis[100001],pred[100001],n;

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

int main()
{
	int i,k,j,max;
	Citire();
	lis[n]=1;
	pred[n]=n+1;
	for(i=n-1;i>=1;i--)
	{
		max=0;k=n+1;
		for(j=i+1;j<=n;j++)
			if((a[j]>a[i])&&(max<lis[j]))
			{
				max=lis[j];
				k=j;
			}
		lis[i]=1+max;
		pred[i]=k;
			
	}
	k=1;
	for(i=2;i<=n;i++)
		if(lis[k]<lis[i])
			k=i;
	ofstream f("scmax.out");
	f<<lis[k]<<"\n";
	
	while(k<n+1)
	{
		f<<a[k]<<" ";
		k=pred[k];
	}
	f<<"\n";
	f.close();
	return 0;
}