Cod sursa(job #2834305)

Utilizator gabriel10tm@gmail.comGabriel Marian [email protected] Data 16 ianuarie 2022 20:17:54
Problema Subsir crescator maximal Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.03 kb
#pragma region
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
#include <unordered_set>
#include <unordered_map>
#include <map>
typedef unsigned long long ull;
typedef long long ll;
typedef unsigned int uint;
#define endl '\n'
using namespace std;
#if 1
#include <fstream>
ifstream fin("scmax.in");
ofstream fout("scmax.out");
#define cin fin
#define cout fout
#endif
#pragma endregion
int a[100001];
int dp[100001];
int T[100001];
int main()
{
	int n;
	cin >> n;
	int lmx = 0,lmxi=0;
	for (int i = 1; i <= n; i++)
		cin >> a[i];
	for (int i = 1; i <= n; i++)
	{
		int mx = 0,mxj=0;
		for (int j = 1; j <= i-1; j++)
			if (a[j] < a[i])
				if(mx < dp[j])
					mx = dp[j],
					mxj = j;
		T[i] = mxj;
		dp[i] = mx + 1;
		if (lmx < dp[i])
			lmx = dp[i],
			lmxi = i;
	}
	cout << lmx;
	vector<int> out;
	int it = lmxi;
	while (T[it])
	{
		out.push_back(a[it]);
		it = T[it];
	}
	out.push_back(a[it]);
	cout << endl;
	for (int i = out.size() - 1; i >= 0; i--)
	{
		cout << out[i] << " ";
	}
}