Cod sursa(job #384136)

Utilizator mihainexMihai Nechita mihainex Data 19 ianuarie 2010 11:46:56
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.59 kb
#include<fstream>
using namespace std;
int main()
{
	int v[100000],l[100000],p[100000],n,i,j,poz;
	ifstream fin("scmax.in");
	ofstream fout("scmax.out");
	fin>>n;
	for(i=1;i<=n;i++)
	   fin>>v[i];
	l[n]=1;
	p[n]=-1;
	for(i=n-1;i>0;--i)
	{
		poz=0;
		for(j=i+1;j<=n;j++)
		  if(v[j]>v[i])
		     if(poz==0)
			   poz=j,p[i]=poz;
			  else
			   if(l[j]>l[poz])
			     poz=j,p[i]=poz;
		if(poz==0)
		  l[i]=1,p[i]=-1;
		 else
		  l[i]=l[poz]+1;
	  }
	poz=1;
	for(i=2;i<=n;i++)
	   if(l[i]>l[poz])
	      poz=i;
	i=poz;
	fout<<l[poz]<<endl;
	while(i!=-1)
	{
		fout<<v[i]<<" ";
		i=p[i];
     }
	return 0;
}