Cod sursa(job #1431011)

Utilizator Nan_Mihai_324CCNan Mihai Nan_Mihai_324CC Data 8 mai 2015 22:56:01
Problema Subsir crescator maximal Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.96 kb
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <set>

using namespace std;

set<int> subsequence;

int subsecventa_recursiv(int* vect, int nr, int* maxim) {
	if(nr == 1) {
		return 1;
	} else {
		int rez, end, i;
		end = 1;
		for(i = 1; i < nr; i++) {
			rez = subsecventa_recursiv(vect, i, maxim);
			if(vect[i-1] < vect[nr-1] && rez + 1 > end) {
				end = end + 1;
				subsequence.insert(vect[i-1]);
				subsequence.insert(vect[nr-1]);
			}
		}
		if(*maxim < end) {
			*maxim = end;
		}
		return end;
	}
}

int main() {
	freopen("scmax.in", "r", stdin);
	freopen("scmax.out", "w", stdout);
	int nr, i;
	int *vect;
	scanf("%d", &nr);
	vect = (int*) malloc(nr*sizeof(int));
	for(i = 0; i < nr; i++) {
		scanf("%d", &vect[i]);
	}
	int maxim = 1;
	subsecventa_recursiv(vect, nr, &maxim);
	printf("%d\n", subsequence.size());
	for (std::set<int>::iterator it=subsequence.begin(); it != subsequence.end(); ++it) {
		printf("%d ", *it);
	}
	printf("\n");
	return 0;
}