Cod sursa(job #2971844)

Utilizator andrei_C1Andrei Chertes andrei_C1 Data 28 ianuarie 2023 10:37:00
Problema Subsir crescator maximal Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.98 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];

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

		ans[--m] = a[pos];
	}
	m = lg;

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