Cod sursa(job #810828)

Utilizator EternalHeroeEternal Heroe EternalHeroe Data 11 noiembrie 2012 06:25:38
Problema Subsir crescator maximal Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.46 kb
#include<fstream>
using namespace std;
ifstream f("scmax.in");
ofstream g("scmax.out");

int n,i,p,j,a[100001],poz[100001],z[100001],maxim=1;
int main(){
	f>>n;
	for(i=1;i<=n;++i)
		f>>a[i];
	z[n]=1;
	p=n;
	poz[n]=n+1;
	for(i=n-1;i>=1;i=i-1)
	{
		z[i]=1;
		for(j=i+1;j<=n;++j)
			if(a[i]<a[j]&&z[i]<z[j]+1)
			{
				z[i]=z[j]+1;
				poz[i]=j;
				if(z[i]>maxim) maxim=z[i],p=i;
			}
	}
	g<<maxim<<"\n";
	while(poz[p])
	{
		g<<a[p]<<" ";
		p=poz[p];
	}
	g<<"\n";
	
}