const int n=1000; //tamaño del vector (0..n-1)
typedef int Tvector[n];
//estructura del vector
struct vector{
int ini;
int fin;
int suma;
};
vector subvector_optimo(Tvector v,int lon,int c,int f){
//Variables locales
vector izq,der,cent; //Se divide el vector en tres subvectores
vector optimo; //valor devuelto por el metodo
int m,i;
int suma=0;
int tamanio_izq,tamanio_der; /*tamaños del subvector izquierdo y
derecho respectivamente*/
if(f-c+1<=lon){ /*Se comprueba si el vector tiene mayor longitud
que el subvector que se esta buscando si la longitud del vector
es menor que la del subvector entonces se suman todas las
posiciones hasta el final del vector*/
for(i=c;i<=f;i++){ //coste lineal
suma=suma+v[i];
};
optimo.ini=c; /*operaciones con coste cte*/
optimo.fin=f;
optimo.suma=suma;
}
else{ /*el vector tiene mayor longitud que la solicitada*/
m=(c+f)/2; /*Se halla el punto medio del vector (coste cte)*/
izq=subvector_optimo(v,lon,c,m); //coste T(n/2)
/*si el vector izquierdo es de menor longitud
que "lon" entonces se amplia por la derecha hasta
llegar a la longitud "lon" pasada por parametro*/
tamanio_izq=izq.fin-izq.ini + 1;
if(tamanio_izq< lon){
while(tamanio_izq<lon){
izq.fin++;
izq.suma+=v[izq.fin];
tamanio_izq++;
}
}
der=subvector_optimo(v,lon,m+1,f); //coste T(n/2)
/*si el vector derecho es de menor longitud que "lon"
entonces se amplia por la izquierda hasta llegar
a la longitud "lon" pasada por parametro*/
tamanio_der=der.fin-der.ini + 1;
if(tamanio_der< lon){
while(tamanio_der<lon){
der.ini--;
der.suma+=v[der.ini];
tamanio_der++;
}
}
cent=subvector_central(v,lon,c,f);
/*Se calcula cual de los tres subvectores tiene
mayor suma*/
/*Todas las operaciones son de coste cte*/
if(izq.suma>=der.suma){
if(izq.suma>=cent.suma)
optimo=izq;
else optimo=cent;
}
else if (der.suma>=cent.suma)
optimo=der;
else optimo=cent;
};
return optimo;
};//fin subvector_optimo
vector subvector_central(Tvector v,int lon,int c,int f){
//variables locales
int m,suma,suma_max;
int inicio,final;/*variables que indican el inicio y el final del
subvector pasando por el centro*/
vector optimo;/*valor devuelto por el metodo*/
m = (c+f)/2; //Se calcula el punto medio del vector
suma_max=INT_MIN; /*Se le asigna el minimo valor de los enteros
para poder hacer las comparaciones
con "suma", ya que los elementos del vector
no valdran nunca el minimo el valor entero*/
suma = 0;
inicio = m-lon+1;
final = m+lon-1; /*operaciones con coste cte*/
if (inicio < 0){
inicio = 0; /*Se inicializa a cero para que no busque
en posiciones inexistentes en el vector*/
};
if (final > n-1){
/*Si se le pasamos una longitud "lon" mas grande que la
mitad del vector,tomando como posicion de inicio "m" nos pasaremos
del rango del vector original. De ahi la asignacion "final = m+lon-
1" que nos da el limite hasta donde podriamos calcular un subvector
de longitud "lon" con inicio en el punto medio "m". Si "final" se
pasa del rango solo podremos calcular n-lon+1 subvectores de
longitud "lon", o lo que es lo mismo, solo podremos calcular
subvectores con inicio entre 0 y n-lon.*/
/*Calculamos el subvector maximo de forma iterativa*/
for(int i=inicio; i<=n-lon ;i++){ //se hara n-lon-inicio+1 veces
suma=0;
for(int j=0;j<lon;j++){ //se hara lon veces
suma=suma+v[j+i];
};
if(suma>=suma_max){
suma_max=suma;
optimo.suma=suma_max;/*operaciones con coste cte*/
optimo.ini=i;
optimo.fin = optimo.ini+lon-1;
};
};
}else{/* "final" cae dentro del rango del vector y por tanto se
pueden calcular todos los posibles subvectores de longitud "lon"
que pasen por el centro (m), incluidos los que tienen como inicio
la mitad del vector (m).*/
/*igual que en el otro caso, se calcula el subvector maximo de
forma iterativa*/
for(int i=inicio; i<=m ;i++){ //se hara m-inicio+1 veces
suma=0;
for(int j=0;j<lon;j++){ //se hara lon veces
suma=suma+v[j+i];
};
if(suma>=suma_max){
suma_max=suma;
optimo.suma=suma_max; /*operaciones con
coste cte*/
optimo.ini=i;
optimo.fin = optimo.ini+lon-1;
};
};
};
return optimo;
}//fin subvector_central
