Cod sursa(job #1012934)

Utilizator bghimisFMI Ghimis Bogdan bghimis Data 19 octombrie 2013 22:11:38
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.84 kb
#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;

#define NMax 100001

int main()
{
	freopen("scmax.in", "r", stdin);
	freopen("scmax.out", "w", stdout);

	int n, i, j; cin >> n;
	int v[NMax];
	for (i = 1; i <= n; ++i)
		cin >> v[i];

	int sol[NMax];
	sol[n] = 1;
 
	int maxim = 0;
	for(i = n - 1; i >= 1; --i)
	{
		sol[i] = 1;
		for(j = i + 1;j <= n; ++j)
			if (v[i] < v[j] && sol[i] < sol[j] + 1)
			{
				sol[i] = sol[j] + 1;
				if (maxim < sol[i])
					maxim = sol[i];
			}
	}

	int suma = 0; vector<int> rezultat;
	for (i = 1; i <= n; ++i)
	{
		if (sol[i] == maxim)
		{
			++suma;
			rezultat.push_back(v[i]);
			--maxim;
		}
	}

	cout << suma << "\n";
	for(vector<int>::const_iterator it = rezultat.begin(); it != rezultat.end(); ++it)
		cout << *it << " ";

	return 0;
}