Cod sursa(job #1431025)

Utilizator Nan_Mihai_324CCNan Mihai Nan_Mihai_324CC Data 8 mai 2015 23:03:44
Problema Subsir crescator maximal Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.55 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 subsecventa_dinamica(int* vect, int nr) {
	int* rez = (int*) malloc(nr*sizeof(int));
	bool* viz = (bool*) malloc(nr*sizeof(bool));
	int i, j, max = 0;
	for(i = 0; i < nr; i++) {
		rez[i] = 1;
		viz[i] = false;
	}
	for(i = 0; i < nr; i++) {
		for(j = 0; j < i; j++) {
			if(vect[i] > vect[j] && rez[i] < rez[j] + 1) {
				rez[i] = rez[j] + 1;
				if(viz[i] == false) {
					subsequence.insert(vect[i]);
					viz[i] = true;
				}
				if(viz[j] == false) {
					subsequence.insert(vect[j]);
					viz[j] = true;
				}
				if(rez[i] > max) {
					max = rez[i];
				}
			}
		}
	}
	free(rez);
	free(viz);
	return max;
}

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_dinamica(vect, nr);
	printf("%d\n", subsequence.size());
	for (std::set<int>::iterator it=subsequence.begin(); it != subsequence.end(); ++it) {
		printf("%d ", *it);
	}
	printf("\n");
	return 0;
}