Cod sursa(job #3339418)

Utilizator vlad_crbsvlad carabas vlad_crbs Data 8 februarie 2026 08:54:17
Problema Subsir crescator maximal Scor 65
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.68 kb
#include <bits/stdc++.h>
using namespace std;

ifstream in("scmax.in");
ofstream out("scmax.out");
int dp[100001], v[100001],t[100001];
void tati(int u) {
	if (u != 0) {
		tati(t[u]);
		out << v[u] << ' ';
	}
}
int main()
{
	int n;
	in >> n;
	for (int i = 0;i < n;i++) {
		in >> v[i];
	}
	dp[0] = 1;
	int sol = 0, k = 0;
	for (int i = 1;i < n;i++) {
		int maxim = 0;
		int p;
		for (int j = 0;j < i;j++) {
			if (v[i] > v[j] && dp[j] > maxim) {
				maxim = dp[j];
				p = j;
			}
		}
		dp[i] = maxim + 1;
		if (dp[i] != 1) {
			t[i] = p;
		}
		else {
			t[i] = 0;
		}
		if (sol < dp[i]) {
			sol = dp[i];
			k = i;
		}
	}
	out << sol << '\n';
	tati(k);
}