Cod sursa(job #1828910)

Utilizator Rocamadour1497Alexandru Martiniuc Rocamadour1497 Data 14 decembrie 2016 01:22:46
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.6 kb
#include <iostream>
#include <fstream>
using namespace std;
ifstream f("scmax.in");
ofstream g("scmax.out");
int main()
{
	int a[100001], b[100001], n, i, j, pre[100001], maxim = 1, maxi;
	f>> n;
	for (i = 1; i <= n; i++) f >> a[i];
	b[n] = 1;
	pre[n] = -1;

	for (i = n - 1; i >= 1; i--)
	{
		b[i] = 1;
		pre[i] = -1;
		for (j = i + 1; j <= n; j++)
		{
			if (a[i] < a[j] && b[i] < b[j] + 1)
			{
				b[i] = b[j] + 1;
				pre[i] = j;
				if (b[i] > maxim) maxim = b[i], maxi = i;
			}
		}
	}
	g << maxim << endl;
	while (maxi>0)
	{
		g << a[maxi] << " ";
		maxi = pre[maxi];
	}
}