Cod sursa(job #2105425)

Utilizator bostanmateiBostan Matei-Calin bostanmatei Data 13 ianuarie 2018 11:20:12
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.83 kb
#include <fstream>
#include <cmath>
#include <algorithm>
#define NMAX 100005

using namespace std;

ifstream cin("scmax.in");
ofstream cout("scmax.out");
struct str {
	int val, pos, t, e;
};
str a[NMAX];
int n;
int main() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> a[i].val;
		a[i].pos = i;
	}
	a[n].e = 1;
	for (int i = n - 1; i > 0; i--) {
		int maxim = 0, source = 0;
		for (int j = i + 1; j <= n; j++) {
			if (a[i].val < a[j].val) {
				if (maxim < a[j].e) {
					source = j;
					maxim = a[j].e;
				}
			}
		}
		a[i].e = maxim + 1;
		a[i].t = source;
	}
	int maxim = 0, pos = 0;
	for (int i = 1; i <= n; i++) {
		if (maxim < a[i].e) {
			maxim = a[i].e;
			pos = i;
		}
	}
	cout << maxim << '\n';
	while (pos) {
		cout << a[pos].val << ' ';
		pos = a[pos].t;
	}
	//system("pause");
}