Cod sursa(job #2752798)

Utilizator mex7Alexandru Valentin mex7 Data 19 mai 2021 17:55:03
Problema Subsir crescator maximal Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.84 kb
#include <bits/stdc++.h>
#define ll long long
#define cin fin
#define cout fout
using namespace std;

ifstream fin("scmax.in");
ofstream fout("scmax.out");
int n, v[100004];
int maxLen[100004], lastInd[100004];

void outputElements(int currInd) {
	if (currInd == lastInd[currInd]) {
		cout << v[currInd] << ' ';
		return;
	}

	outputElements(lastInd[currInd]);
	cout << v[currInd] << ' ';
}

int main() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> v[i];
		maxLen[i] = 1;
		lastInd[i] = i;
	}

	for (int i = 1; i <= n; i++)	
		for (int j = i + 1; j <= n; j++)
			if (v[i] < v[j] && maxLen[i] + 1 > maxLen[j]) {
				maxLen[j] = maxLen[i] + 1;
				lastInd[j] = i;
			}

	int maxIndex = 0;
	for (int i = 1; i <= n; i++) 
		if (maxLen[i] > maxLen[maxIndex])
			maxIndex = i;

	cout << maxLen[maxIndex] << '\n';
	outputElements(maxIndex);
	
	return 0;
}