Cod sursa(job #824149)

Utilizator roxyrooxyBlaj Roxana roxyrooxy Data 25 noiembrie 2012 22:06:44
Problema Subsir crescator maximal Scor 0
Compilator c Status done
Runda Arhiva educationala Marime 0.97 kb
#include <stdio.h>
#include <stdlib.h>

int *v, n, *M, *P;
int BinarySearch(int x, int min, int max) {
	int mid = (min + max) / 2;

	if (min > max) return 0;

	if (v[M[min]] >= x) return min-1;
	if (v[M[max]] < x) return max;
	if (v[M[mid]] < x) return mid;
	if (v[M[mid]] >= x) return BinarySearch(x, min, mid);

	return 0;
}

void show(FILE *out, int i, int j) {
	if (j == 0) return;

	show(out, P[i], j-1);
	fprintf(out, "%d ", i);
}

int main(int argc, char *argv[]) {
	FILE *in, *out;
	int i, j, L = 0;
	in = fopen(argv[1], "r");
	out = fopen(argv[2], "w");
	fscanf(in, "%d", &n);

	v = (int*)malloc((n+1) * sizeof(int));
	M = (int*)malloc((n+1) * sizeof(int));
	P = (int*)malloc((n+1) * sizeof(int));
	for (i = 1; i <= n; i++) {
		fscanf(in, "%d", &v[i]);
	}

	for (i = 1; i <= n; i++)
	{
		j = BinarySearch(v[i], 1, L);

		P[i] = M[j];
		if (j == L || v[i] < v[M[j+1]]) {
			M[j+1] = i;
			L = ((L > j + 1) ? L : j + 1);
		}
	}

	show(out, M[L], L);

	fclose(in);
	fclose(out);
	return 0;
}