Cod sursa(job #3242403)

Utilizator Commander_XDunel Stefan-Octavian Commander_X Data 11 septembrie 2024 21:37:29
Problema Subsir crescator maximal Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.84 kb
//https://www.infoarena.ro/problema/scmax
#include <fstream>
#include <vector>

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

using namespace std;

int max(int a, int b)
{
	return a > b ? a : b;
}

vector<int> v, dp, t;
int last;
void drum(int u)
{
	if (u != -1)
	{
		drum(t[u]);
		fout << v[u] << ' ';
	}
}
int main()
{
	int n, maxim = 0, p_maxim = 0, p;
	fin >> n;
	v.resize(n);
	t.resize(n, -1);
	dp.resize(n, 1);
	for (int i = 0; i < n; ++i)
		fin >> v[i];

	for (int i = 1; i < n; ++i)
	{
		for (int j = 0; j < i; ++j)
			if (v[j] < v[i] && dp[j] + 1 > dp[i])
			{
				dp[i] = dp[j] + 1;
				p = j;
			}
		if (dp[i] != 1)
			t[i] = p;
		else
			t[i] = -1;
		if (dp[i] > maxim)
		{
			maxim = dp[i];
			p_maxim = i;
		}
	}
	fout << maxim << '\n';
	last = v[p_maxim];
	drum(p_maxim);
}