Cod sursa(job #808995)

Utilizator vlad.bandacBandac Vlad Constantin vlad.bandac Data 7 noiembrie 2012 19:31:03
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.92 kb
#include <fstream>
#define Nmax 100004
using namespace std;

ifstream fin("scmax.in");
ofstream fout("scmax.out");

int a[Nmax],lgmax[Nmax],urm[Nmax];
int n;

void citire();
void pd();

void citire(){
	int i;
	fin>>n;
	for(i=0;i<n;i++)
		fin>>a[i];
}

int main(){
	citire();
	pd();
	fout.close();
	return 0;
}

void pd(){
	int lungmx,j,i,lungmxtot=0,maxi;
	lgmax[n-1]=1;
	for(i=n-2;i>=0;i--){
		lungmx=1;
		for(j=i+1;j<=n-1;j++)
			if(a[i]<a[j])//am gasit solutie
				if(1+lgmax[j]>lungmx)
					lungmx=1+lgmax[j];
				
		lgmax[i]=lungmx;//1 daca nu s-a gasit solutie si >1 daca am gasit
		if(lungmx>lungmxtot){
			lungmxtot=lungmx;
			maxi=i;
		}
	}
	/*for(j=0;j<n;j++)
		fout<<lgmax[j]<<' ';
	fout<<lungmxtot;*///afisarea s-a realizat cu succes
	
	//afisarea propiuzisa
	fout<<lungmxtot<<'\n';
	for(i=maxi;i<n;i++){
		if(lgmax[i]==lungmxtot){
			fout<<a[i]<<' ';
			lungmxtot--;
		}
	}
}