Cod sursa(job #1244440)

Utilizator radudorosRadu Doros radudoros Data 17 octombrie 2014 15:43:36
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.75 kb
#include <fstream>
using namespace std;


int l[100001];
int a[100001];
ifstream fin("scmax.in");
ofstream fout("scmax.out");




int main()
{
	int n;
	fin >> n;
	for (int i = 1; i <= n; i++)
	{
		fin >> a[i];
	}
	l[n] = 1;
	int lmax = 1;
	for (int i = n - 1; i >= 1; i--)
	{
		int max = 0;
		for (int j = i + 1; j <= n; j++)
		{
			if (a[j] > a[i] && l[j] > max)
				max = l[j];
		}
		l[i] = max + 1;
		if (l[i] > lmax)
		{
			lmax = l[i];
		}
	}
	fout << lmax << '\n';
	/*determinarea drumului in O(n)*/

	int p = 1;
	while (l[p] != lmax)
		p++;
	fout << a[p] << ' ';
	int aux = p;
	lmax--;
	while (lmax)
	{
		p++;
		if (l[p] == lmax && a[aux] < a[p])
		{
			lmax--;
			aux = p;
			fout << a[p] << ' ';
		}
	}

}