/*
	Divide & Conquer
	
	Busqueda del elemento mayor en forma recursiva
	
	Autor : Ricardo Markiewicz
	Version : 1.0.0
	
	ChangeLog :
	
	18-06-2002 - Inicio
*/

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

/* CANTIDAD debe ser un numero tal que : 2^k = CANTIDAD */
#define CANTIDAD 16

int Maximo(int *, int, int);


int main(int argc, char *argv[])
{
	int v[CANTIDAD], i;
	
	srand(time(NULL));

	printf("Array = {");
	for(i=0; i<CANTIDAD; i++) {
		v[i] = rand()%255;
		printf("%d", v[i]);
		if (i<CANTIDAD-1)
			printf(",");
	}
	printf("}\n");
	
	printf("Maximo : %d\n", Maximo(v, 0, CANTIDAD-1));
	
	return EXIT_SUCCESS;
}

/*
   v = vector donde buscar
   p = posicion del primer elemento
   u = posicion del ultimo elemento
*/
int Maximo(int *v, int p, int u)
{
	int medio, max1, max2;

	/* Tomo como caso base tener 2 elementos */
	if ((u-1) == p) {
		return (v[u]>v[p])?v[u]:v[p];
	} else {
		/* Como tengo mas de 2 elementos aplico recursividad */
		
		/* Calculo la posicion central del subvector */
		medio = p + (u-p) / 2;

		/* Calculo el maximo de la parte inferior del subvector */
		max1 = Maximo(v, p, medio);
		
		/* Calculo el maximo de la parte superior del subvector */
		max2 = Maximo(v, medio+1, u);
		
		
		/* Retorno el elemento mayor de ambos subvectores */
		if (max1 < max2)
			return max2;
		
		return max1;
	}
}