Cod sursa(job #1189439)

Utilizator StefanaPpStefana Popa StefanaPp Data 22 mai 2014 20:35:18
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.64 kb
#include<fstream>
using namespace std;
ifstream fin("scmax.in");
ofstream fout("scmax.out");

int main()
{
	int n, v[100005], sub[100005], i, j, lg=1, poz;
	fin >> n;
	for (i = 1; i <= n; i++)
		fin >> v[i];
	sub[n] = 1;
	for (i = n-1; i >= 1; i--)
	{
		sub[i] = 1;
		for (j = i + 1; j <= n; j++)
		{
			if (v[i] < v[j] && sub[i] <= sub[j])
				sub[i] = sub[j] + 1;
		}
		if (sub[i]>lg)
		{
			lg = sub[i];	poz = i;
		}
	}
	fout << lg << '\n';
	if (lg > 0)
		fout << v[poz] << ' ';
	lg--;
	for (i = poz+1; i <= n && lg>0; i++)
	{
		if (sub[i] == lg && v[poz]<v[i])
		{
			fout << v[i] << ' ';
			lg--;
			poz = i;
		}
	}
}