Cod sursa(job #431195)

Utilizator undogSavu Victor Gabriel undog Data 31 martie 2010 19:15:31
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.57 kb
#include <fstream>

using namespace std;

ofstream out("scmax.out");

int v[100005];
	
int m[100005];
int s[100005];

void print(int i){
	if(s[i])
		print(s[i]);
	out<<v[i]<<' ';
}

int main(){
	
	ifstream in("scmax.in");
	
	
	int i,j,n;
	
	in>>n;
	
	for(i=1;i<=n;i++){
		in>>v[i];
		m[i]=1;
	}
	
	int max=0;
	
	for(i=2;i<=n;i++){
		max=0;
		for(j=1;j<i;j++)
			if(v[i]>v[j]&&m[j]>max){
				max=m[j];
				s[i]=j;
			}
		if(max)
			m[i]=max+1;
	}
	
	int pos;
	max=0;
	for(i=1;i<=n;i++)
		if(m[i]>max){
			max=m[i];
			pos=i;
		}
	out<<max<<'\n';
	print(pos);
	out<<'\n';

	return 0;
}