Cod sursa(job #486905)

Utilizator mateiuliIulian mateiuli Data 23 septembrie 2010 09:05:37
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.61 kb
#include <fstream.h>
ifstream fin("scmax.in");
ofstream fout("scmax.out");
int v[100001],n;
 
int main() {
	int l[100001], i, j, max, t;
	fin>>n;
	for(i=1;i<=n;i++)
		fin>>v[i];
	fin.close();
	
	l[n] = 1;

	for(i=n-1; i>=1; i--) {
		max = 0;
		for(j=i+1;j<=n;j++) {
			if(v[i] < v[j] && max < l[j])
					max = l[j];
			l[i] = 1+max;
		}	
	}
	
	max = 0;
	for(i=1;i<=n; i++) {
		if(max < l[i]) {
			max = l[i];
			t=i;
		}
	}
	
	fout<<max<<'\n'<<v[t]<<' ';
	max--;
	for(i=t+1;i<=n;i++) {
		if(l[i] == max) {
			fout<<v[i]<<' ';
			max--;
		}
		if(max==0)
			break;
	}
	fout.close();
}