Cod sursa(job #635423)

Utilizator comananamariaComan Ana-Maria comananamaria Data 19 noiembrie 2011 11:24:37
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.62 kb
#include<fstream>

using namespace std;

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

int n,v[100001],l[100001];

int main(){
	in>>n;
	for(int i=1;i<=n;i++)
		in>>v[i];
	l[n]=1;
	for(int i=n-1;i>=1;i--){
		int max=0;
		for(int j=i+1;j<=n;j++)
			if(v[i]<v[j])
				if(max<l[j])
					max=l[j];
		l[i]=max+1;
	}
	int lmax=l[1],pmax=1,ult=v[1];
	for(int i=2;i<=n;i++)
		if(lmax<l[i]){
			lmax=l[i];
			pmax=i;
			ult=v[i];
		}
	out<<lmax<<endl;
	out<<v[pmax]<<" ";
	lmax--;
	for(int i=pmax+1;i<=n;i++)
		if(l[i]==lmax && v[i]>ult){
			out<<v[i]<<" ";
			ult=v[i];
			lmax--;
		}
	return 0;
}