Cod sursa(job #704260)

Utilizator Black_TigerSima Cristian Black_Tiger Data 2 martie 2012 17:09:30
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.68 kb
#include<iostream>
#include<fstream>

using namespace std;

ifstream f("scmax.in");
ofstream g("scmax.out");

int a[100000],v[100000],p[100000];

void drum(int i){
	
	if(p[i]== 0 )
		g<<v[i]<<" ";
	else
		{g<<v[i]<<" ";
		return drum(p[i]);
		}
}

int main(void){

	int n,i,j,ml,max;
	
	f>>n;

	for(i=1;i<=n;i++)
	f>>v[i];
	
	a[n]=1;
	max=0;
	int ind;
	
	for(i=n-1;i>0;i--)
	{
		p[i]=0;
		ml=0;
		for(j=i;j<=n;j++)
		{
			if(v[i]<v[j] && a[j]>ml)
			{
				ml=a[j];
				p[i]=j;
			}
		}
		ml++;
		if(ml>a[i])
		{
			a[i]=ml;
		}
		
		if(ml>max)
			{
				max=ml;
		
		ind=i;
		}
		
	}
	
	
	g<<max<<endl;
	i=ind;

	drum(i);
return 0;
}