Pagini recente » Cod sursa (job #2793645) | Cod sursa (job #527414) | Monitorul de evaluare | Cod sursa (job #2783998) | Cod sursa (job #1229239)
#include <stdio.h>
#define MAX 1000
FILE *fin, *fout;
void read();
void dynamicProgramming();
void write();
int vec[ MAX ], n, best[ MAX ];
int main() {
read();
dynamicProgramming();
write();
return 0;
}
void read() {
int i;
fin = fopen("scmax.in","r");
fscanf(fin, "%d", &n);
for(i = 0; i < n; i++) {
fscanf(fin, "%d", &vec[ i ]);
}
fclose( fin );
};
void dynamicProgramming() {
int i,j, max;
best[ n - 1 ] = 1;
for(i = n - 2; i >= 0; i--) {
max = 0;
for(j = i + 1; j < n; j++) {
if(vec[ i ] < vec[ j ] && best[ j ] > max) {
max = best[ j ];
}
}
best[i] = 1 + max;
}
};
void write() {
int i, maxBest = best[ 0 ], pos, k;
fout = fopen("scmax.out","w");
pos = 0;
for(i = 1; i < n; i++) {
if(best[i] > maxBest) {
maxBest = best[i];
pos = i;
}
}
fprintf(fout, "%d\n", maxBest);
fprintf(fout, "%d ", vec[pos]);
for(k = 0; k < n; k++) {
if(best[ k ] == maxBest-1 && vec[ pos ] < vec[ k ]) {
fprintf(fout, "%d ", vec[k]);
maxBest--;
}
}
fclose( fout );
};