Pagini recente » Cod sursa (job #1318264) | Cod sursa (job #2090688) | Cod sursa (job #2952485) | Cod sursa (job #376409) | Cod sursa (job #1431025)
#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;
}