Cod sursa(job #524522)

Utilizator GDanielDaniel Gavril GDaniel Data 22 ianuarie 2011 10:15:31
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.69 kb
#include <fstream.h>

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

long n, maxlg, indicemaxlg, max, lg[1000001], u[100001], a[100001], nrr; 
 
int main() 
{ 
	fin >> n;
	for (long i = 1; i <= n; i ++)
		fin >> a[i]; 
	
	max = 0;
	for (long j = n; j >= 1; j --) 
	{
		maxlg = 0;
		indicemaxlg = 0; 
		
		for (long i = j + 1; i <= n; i++) 
			if (maxlg < lg[i] && a[i] > a[j]) 
			{
				maxlg = lg[i];
				indicemaxlg = i; 
			} 
		
		lg[j] = maxlg + 1; 
		u[j] = indicemaxlg; 
		
		if (lg[j] > max) 
		{
			max = lg[j];
			nrr = j;
		}
	}
	
	fout << max << '\n';
	while (nrr != 0) 
	{ 
		
		fout << a[nrr] << " ";
		nrr = u[nrr]; 
	} 
return 0; 
}