Cod sursa(job #1420772)

Utilizator gabi.cristacheGabi Cristache gabi.cristache Data 18 aprilie 2015 22:22:31
Problema Subsir crescator maximal Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.81 kb
#include <fstream>
#include <string.h>

#define SZ 100010 

using namespace std;

int max(int a, int b) {
	return a > b ? a : b;
}

int best[SZ], prev[SZ], val[SZ];
int N;

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


int main() {
	
	memset(best, 1, SZ);

	fin >> N;
	int maxIndex = 0;
	int maxBest = 0;
	for (int i = 1; i <= N; ++i) {
		fin >> val[i];

		for (int j = 1; j < i; ++j) {
			if (val[j] < val[i] && 1 + best[j] > best[i]) {
				best[i] = 1 + best[j];
				prev[i] = j;
			}
		}

		if (best[i] > maxBest) {
			maxBest = best[i];
			maxIndex = i;
		}
	}

	int count = 0;
	int u = maxIndex;
	while (u != 0) {
		best[SZ - 1 - count] = val[u];
		u = prev[u];
		++count;
	}

	fout << count << '\n';
	for (int i = 1; i <= count; ++i) {
		fout << best[SZ - 1 - count + i] << ' ';
	}
	fout << '\n';

	return 0;
}