Cod sursa(job #3242402)

Utilizator Commander_XDunel Stefan-Octavian Commander_X Data 11 septembrie 2024 21:25:50
Problema Subsir crescator maximal Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.91 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;
int last;
void show(int i, int cnt_maxim)
{
	if (cnt_maxim == 0 || i < 0)
		return;
	if (v[i] < last && dp[i] == cnt_maxim)
	{
		last = v[i];
		show(i - 1, cnt_maxim - 1);
		fout << v[i] << ' ';
	}
	else
		show(i - 1, cnt_maxim);
}
int main()
{
	int n, maxim = 0, p_maxim = 0;
	fin >> n;
	v.resize(n);
	dp.resize(n, 1);
	for (int i = 0; i < n; ++i)
		fin >> v[i];

	for (int i = 0; i < n; ++i)
	{
		for (int j = 0; j < i; ++j)
			if (v[j] < v[i])
				dp[i] = max(dp[i], dp[j] + 1);
		if (dp[i] > maxim)
		{
			maxim = dp[i];
			p_maxim = i;
		}
	}
	fout << maxim << '\n';
	last = v[p_maxim];
	show(p_maxim - 1, maxim - 1);
	fout << v[p_maxim];
}