Cod sursa(job #2910164)

Utilizator radu.seitanSeitan Radu-Catalin radu.seitan Data 18 iunie 2022 16:55:07
Problema Subsir crescator maximal Scor 60
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.87 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>

#define NMAX 100000

using namespace std;

vector<int> numbers;
int n = 0;

int best[NMAX], smax = 0, sol = 0, pos[NMAX], p;

void algo()
{
	best[n] = 1;
	pos[n] = -1;
	smax = 1;
	p = n;

	for(auto i = n - 1; i >= 1; --i)
	{
		best[i] = 1;
		pos[i] = -1;

		for(auto j = i + 1; j <= n; ++j)
		{
			if(numbers[i] < numbers[j] && best[i] < best[j] + 1)
			{
				best[i] = best[j] + 1;
				pos[i] = j;
				if(best[i] > smax)
				{
					smax = best[i];
					p = i;
				}
			}
		}
	}

}

int main()
{
	ifstream fin("scmax.in");
	ofstream fout("scmax.out");

	auto aux = 0;
	fin >> n;
	for(auto i = 0; i < n; i++)
	{
		fin >> aux;
		numbers.push_back(aux);
	}

	algo();

	int k = p;

	fout << smax << '\n';

	while(k != -1)
	{
		fout << numbers[k] << " ";
		k = pos[k];
	}


	fin.close();
	fout.close();
	return 0;
}