Cod sursa(job #717254)

Utilizator BarracudaFMI-Alex Dobrin Barracuda Data 19 martie 2012 19:30:11
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.79 kb
#include<fstream>
using namespace std;

const char In[]="scmax.in";
const char Out[]="scmax.out";
const int dim=100002;

ifstream f(In);
ofstream g(Out);
int a[dim],L[dim],maxu,pos,n;
void citire(){
	f>>n;
	for(register int i=1;i<=n;++i)
		f>>a[i];
}
void scmax(){
	L[n]=1;
	for(register int i=n-1;i>=1;--i){
		maxu=0;
		for(register int  j=i+1;j<=n;++j){
			
			if(a[j]>a[i] && L[j]>maxu){
				
				maxu=L[j];
			}
		}
		L[i]=maxu+1;
	}
	maxu=L[1];
	pos=1;
	for(register int k=1;k<=n;k++){
		if(L[k]>maxu){
			maxu=L[k];
			pos=k;
		}
	}
}
void abracaddabra(){
	g<<maxu<<"\n";
	g<<a[pos]<<" ";
	for(register int i=pos+1;i<=n;++i)
		if(L[i]==maxu-1 && a[i]>a[pos]){
			g<<a[i]<<" ";
			--maxu;
		}
}
int main (){
	citire();
	scmax();
	abracaddabra();
	return 0;
}