Cod sursa(job #2812341)

Utilizator sireanu_vladSireanu Vlad sireanu_vlad Data 4 decembrie 2021 13:46:24
Problema Subsir crescator maximal Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.67 kb
#include <fstream>
using namespace std;

ifstream in("scmax.in");
ofstream out("scmax.out");

int n, x[100001], dp[100001], pre[100001];

void read()
{
	in >> n;
	for(int i = 1; i <= n; ++i)
		in >> x[i];
}

int best(int k)
{
	int b = 0;
	for(int i = k + 1; i <= n; ++i)
		if(x[k] < x[i] && dp[i] > b)
			b = dp[i], pre[k] = i; 
	return b + 1;
}

void afis()
{
	int sol = 0, p;
	for(int i = 1; i <= n; ++i)
		if(sol < dp[i])
			sol = dp[i], p = i;
	out << sol << '\n';
	while(sol--)
	{
		out << x[p] << ' ';
		p = pre[p];
	}
}

int main()
{
	read();

	dp[n] = 1;
	for(int i = n-1; i > 0; --i)
		dp[i] = best(i);

	afis();
	return 0;
}