Cod sursa(job #2035496)

Utilizator robuvedVictor Robu robuved Data 9 octombrie 2017 15:55:16
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.73 kb
#include <fstream>
#include <stack>
using namespace std;

ifstream in("scmax.in");
ofstream out("scmax.out");
#define MAX 100000
int v[MAX], dp[MAX], pr[MAX];
int main()
{
	int N;
	in >> N;
	for (int i = 0; i < N; i++)
	{
		in >> v[i];
	}
	int max_i = -1;
	for (int i = 0; i < N; i++)
	{
		dp[i] = 0;
		pr[i] = -1;
		for (int j = 0; j < i; j++)
		{
			if (v[j] < v[i] && dp[j] > dp[i])
			{
				dp[i] = dp[j];
				pr[i] = j;
			}
		}
		dp[i]++;
		if (max_i <0 || dp[i] > dp[max_i])
		{
			max_i = i;
		}
	}
	out << dp[max_i] << '\n';
	stack<int> s;
	s.push(v[max_i]);

	while (pr[max_i] >= 0)
	{
		max_i = pr[max_i];
		s.push(v[max_i]);
	}
	while (!s.empty())
	{
		out << s.top() << ' ';
		s.pop();
	}
}