Cod sursa(job #2963590)

Utilizator NiffSniffCojocaru Calin Marcu NiffSniff Data 11 ianuarie 2023 16:10:14
Problema Subsir crescator maximal Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.89 kb
#include <fstream>
using namespace std;
string file = "scmax";
ifstream cin (file + ".in");
ofstream cout (file + ".out");
const int N = 100000;
int v[N + 1], lung[N + 1];

void refac_subsir(int pozCurenta, int lungime, int val)
{
	if (lungime)
	{
		if (lung[pozCurenta] == lungime && v[pozCurenta] < val)
		{
			refac_subsir(pozCurenta - 1, lungime - 1, v[pozCurenta]);
			cout << v[pozCurenta] << ' ';
		}
		else
		{
			refac_subsir(pozCurenta - 1, lungime, val);
		}
	}
}
int main()
{
	int n, pozLungMax(1);
	cin >> n;
	for (int i = 1; i <= n; i++)
	{
		int l_jmax(0);
		cin >> v[i];
		for (int j = 1; j < i; j++)
		{
			if (v[j] < v[i])
			{
				l_jmax = max(l_jmax, lung[j]);
			}
		}
		lung[i] = l_jmax + 1;
		if (lung[i] > lung[pozLungMax])
			pozLungMax = i;
	}
	cout << lung[pozLungMax] << endl;
	refac_subsir(pozLungMax, lung[pozLungMax], v[pozLungMax] + 1);
}