Cod sursa(job #3133037)

Utilizator daristyleBejan Darius-Ramon daristyle Data 24 mai 2023 22:32:19
Problema Subsir crescator maximal Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.76 kb
#include <fstream>

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

const int N_MAX = 1e6;
int v[N_MAX + 1], sclen[N_MAX + 1];

int main() {
	int n;
	fin >> n;
	for(int i = 0; i < n; ++i)
		fin >> v[i];

	v[n] = sclen[n] = 0;
	for(int i = n - 1; i >= 0; --i){
		int pos_max = n;
		for(int j = i; j < n; ++j)
			if(v[i] < v[j])
				if(sclen[j] > sclen[pos_max])
					pos_max = j;

		sclen[i] = sclen[pos_max] + 1;
	}

	int pos_max = n;
	for(int i = 0; i < n; ++i)
		if(sclen[pos_max] < sclen[i])
			pos_max = i;

	fout << sclen[pos_max] << '\n';

	int i = pos_max, nxt;
	while(sclen[i]){
		fout << v[i] << ' ';

		nxt = i + 1;
		while(sclen[nxt] != sclen[i] - 1)
			++nxt;

		i = nxt;
	}
	fout.put('\n');

	fin.close();
	fout.close();
	return 0;
}