Cod sursa(job #396688)

Utilizator cezyGrigore Cezar cezy Data 15 februarie 2010 18:50:26
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.77 kb
#include<fstream>
#include<algorithm>
using namespace std;
ofstream fout("scmax.out");
const int nmax=100005;
int best[nmax],v[nmax],poz[nmax];
int n;
void citire ()
{
	int i;
	ifstream fin("scmax.in");
	fin>>n;
	for(i=1;i<=n;i++)
		fin>>v[i];
	fin.close ();
}
void det_poz (int k)
{
	fout<<v[k]<<' ';
	if(poz[k]!=k) det_poz(poz[k]);
}
int main ()
{
	int i,j;
	citire();
	best[1]=1;
	poz[1]=1;
	int maxim=1,p=1,t=0;
	for(i=2;i<=n;i++)
	{
		best[i]=1;poz[i]=i;
		for(j=1;j<=i;j++)
			if(v[i]>v[j] && best[i]<best[j]+1) { best[i]=best[j]+1;poz[i]=j;  }
		if(maxim<best[i]) {maxim=best[i];p=i;}
	}
	fout<<maxim<<"\n";
	while(p!=poz[p])
	{
		best[++t]=v[p];
		p=poz[p];
	}
	best[++t]=v[p];
	for(i=t;i>=1;i--)
		fout<<best[i]<<' ';
	fout.close ();
}