Cod sursa(job #597120)

Utilizator ionutmodoModoranu Ionut-Vlad ionutmodo Data 21 iunie 2011 10:56:35
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.73 kb
#include<fstream>
using namespace std;
int x[100000],lis[100000],next[100000];
int main ()
{
	int n,i,j,maxim,poz;
	
	ifstream fin("scmax.in");
	fin>>n;
	for(i=1; i<=n; i++)
		fin>>x[i];
	
	fin.close();
	
	ofstream fout("scmax.out");
	//maxim = poz = 0;
	
	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]=maxim+1;
		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;
}