Pagini recente » Cod sursa (job #1023941) | Cod sursa (job #753325) | Cod sursa (job #2000757) | Cod sursa (job #2241540) | Cod sursa (job #489098)
Cod sursa(job #489098)
#include <stdio.h>
#define NMAX 256
#define infile "scmax.in"
#define outfile "scmax.out"
int s[NMAX], n, vals[NMAX], ll;
void read_data() {
FILE *fis = fopen(infile, "r");
int i;
fscanf(fis, "%d", &n);
for (i = 0; i < n; i++)
fscanf(fis, "%d", &s[i]);
fclose(fis);
}
//returns a position
int binary_search(int nr) {
int left, right, m;
left = 0;
right = ll;
while (left <= right) {
m = (right + left) / 2;
//if (vals[m] <= nr)
if (vals[m] < nr)
left = m + 1;
else
right = m - 1;
}
return left;
}
void write_data() {
FILE *fis = fopen(outfile, "w");
int j;
fprintf(fis, "%d\n", ll+1);
for (j = 0; j <= ll; j++)
fprintf(fis, "%d ", vals[j]);
fprintf(fis, "\n");
fclose(fis);
}
int main() {
int i, pos;
read_data();
vals[0] = s[0];
ll = 0;
for (i = 1; i < n; i++) {
pos = binary_search(s[i]);
if (pos == ll + 1) {
ll++;
vals[ll] = s[i];
} else {
vals[pos] = s[i];
}
}
write_data();
return 0;
}