Cod sursa(job #2971849)

Utilizator andrei_C1Andrei Chertes andrei_C1 Data 28 ianuarie 2023 10:43:16
Problema Subsir crescator maximal Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.89 kb
#include <bits/stdc++.h>

using namespace std;

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

const int NMAX = 1e5;

int n;
int a[NMAX + 1];
int dp[NMAX + 1]; // dp[i] =def= lungimea subsirului crescator de lungime maxima car se termina cu elementul v[i].
int ans[NMAX + 1];

int main() {
	fin >> n;
	for(int i = 1; i <= n; i++) {
		fin >> a[i];
	}

	dp[1] = 1;
	for(int i = 2; i <= n; i++) {
		int mx = 0;
		for(int j = 1; j < i; j++) {
			if(a[j] < a[i]) {
				mx = max(mx, dp[j]);
			}
		}

		// mx - optim
		dp[i] = mx + 1;
	}

	int pos = 1;
	for(int i = 2; i <= n; i++) {
		if(dp[i] > dp[pos]) {
			pos = i;
		}
	}

	int lg = dp[pos];
	fout << lg << '\n';

	int m = lg;
	ans[m] = a[pos];

	for(int i = pos - 1; i >= 1; i--) {
		if(a[i] < a[pos] && dp[i] + 1 == dp[pos]) {
			ans[--m] = a[i];
			pos = i;
		}
	}

	m = lg;

	for(int i = 1; i <= m; i++) {
		fout << ans[i] << " ";
	}
	return 0;
}