Cod sursa(job #2905728)

Utilizator _Tudor_Tudor C _Tudor_ Data 23 mai 2022 13:19:12
Problema Subsir crescator maximal Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.77 kb
#include <iostream>
#include <fstream>

constexpr int Nmax = 100005;
int arr[Nmax];
int len[Nmax];
int prev[Nmax];

int main()
{
	std::ifstream fin("scmax.in");
	std::ofstream fout("scmax.out");
	
	int n;
	fin >> n;
	for (int i = 0; i < n; i++)
		fin >> arr[i];

	for (int i = n - 1; i >= 0; i--)
	{
		len[i] = 1;
		int len_max = 0;
		int ind = -1;
		for (int j = i + 1; j < n; j++)
		{
			if (arr[i] < arr[j] && len[j] > len_max)
			{
				len_max = len[j];
				ind = j;
			}
		}
		if (ind != -1)
			len[i] += len[ind];
		prev[i] = ind;
	}

	int len_max = 0;
	int ind_max;

	for (int i = 0; i < n; i++)
	{
		if(len[i] > len_max)
		{
			len_max = len[i];
			ind_max = i;
		}
	}

	fout << len_max << '\n';
	while (ind_max != -1)
	{
		fout << arr[ind_max] << ' ';
		ind_max = prev[ind_max];
	}
}