Cod sursa(job #597122)

Utilizator simaghitaSima Gheorghe Eugen simaghita Data 21 iunie 2011 11:02:02
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.67 kb
#include<fstream>
using namespace std;
int x[100001],lis[100001],next[100001],n;

int main()
{
	int i,j,maxim,poz;
	
	ifstream f("scmax.in");
	f>>n;
	for(i=1;i<=n;i++)
		f>>x[i];
	f.close();
	
	ofstream fout("scmax.out");
	
	lis[n]=1;
	next[n]=n+1;
	for(i=n-1;i>0;i--)
	{
		maxim=0;poz=n+1;
		for(j=i+1;j<=n;j++)
		{
			if(x[j]>x[i] && maxim<lis[j])
			{
				maxim=lis[j];
				poz=j;
			}
		}
		lis[i]=1+maxim;
		next[i]=poz;
	}
	maxim=poz=0;
	for(i=1;i<=n;i++)
	{
		if(maxim<lis[i])
		{
			maxim=lis[i];
			poz=i;
		}
	}
	fout<<maxim<<"\n";
	
	while(poz!=n+1)
	{
		fout<<x[poz]<<" ";
		poz=next[poz];
	}
	fout.close();
	return 0;
}