Cod sursa(job #1951535)

Utilizator MariusTestBroboana Marius MariusTest Data 3 aprilie 2017 18:06:13
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.62 kb
#include <fstream>
using namespace std;

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

int main() {
    unsigned long long v[100000], l[100000], poz[100000], m;
	unsigned i, j, n, prim;
	fin >> n;
	for (i = 1; i <= n; i++)
		fin >> v[i];
	for (i = n; i >= 1; i--) {
		l[i] = 1;
		poz[i] = 0;
		for (j = i + 1; j <= n; j++)
			if (v[i] < v[j] && l[i] < 1 + l[j]) {
				l[i] = 1 + l[j];
				poz[i] = j;
			}
		if (m < l[i]) {
			m = l[i];
			prim = i;
		}
	}
	fout << m << '\n';
	for (i = prim; i >= 1; i = poz[i])
		fout << v[i] << ' ';
	fout << '\n';
	fin.close();
	fout.close();
	return 0;
}