Algoritmia/Apéndice B: implementación en C

Capítulo 3: divide y vencerás

Subvector de suma máxima

 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