Cod sursa(job #2509529)

Utilizator VladAdrianaVlad Adriana VladAdriana Data 14 decembrie 2019 12:35:20
Problema Subsir crescator maximal Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.63 kb
#include <fstream>
#include <algorithm>
using namespace std;
ifstream fin("scmax.in");
ofstream fout("scmax.out");
int n, v[100005], dp[100005], pre[100005], maxi, maxpoz,nr ,aux[100005];
int main()
{
	int i, j;
	fin >> n;
	for(i=1;i<=n;i++)
	{
		fin >> v[i];
		dp[i] = 1;
		for (j = 1; j < i; j++)
			if (v[j] < v[i] && dp[j] + 1>dp[i])
			{
				dp[i] = dp[j] + 1;
				pre[i] = j;
			}
		if (maxi < dp[i])
		{
			maxi = dp[i];
			maxpoz = i;
		}
	}
	fout << maxi<<'\n';
	while (maxpoz)
	{
		aux[++nr] = v[maxpoz];
		maxpoz = pre[maxpoz];
	}
	for (i = nr; i > 0; i--)
		fout << aux[i] << ' ';
	return 0;
}