Rizando el rizo en Divide y Venceras, ¿coste lineal?

Archivado
¡Hola!

Tengo un codigo divide y venceras que calcula la subsecuencia de suma maxima de un vector en coste O(nLogn), y me han propuesto pasarlo a O(n), es decir, coste lineal, y que siga siendo divide y venceras. Pero estoy mas perdido que una vaca en un garaje...¿alguien me aporta alguna idea?

Subsecuencia de suma maxima quiere decir el numero maximo que se puede conseguir sumando elementos consecutivos de un vector. Por ejemplo, si un vector es [5,-9,8,12,-20], la subsecuencia de suma maxima es 20 (8+12). Si fuese [5,-22,19,-10,15] entonces seria 24(19-10+15).

A ver si algun genio de la algoritmia me da una pistita...¡Gracias!
Hola, la verdad es que no me acordaba mucho de esto, pero encontré en mi libro de algoritmia un ejemplo de subsecuencia máxima recursivo que tiene un tiempo lineal:

Copio y pego del libro: "Estructura de datos en Java. Mark allen Weiss"

El algoritmo recursivo para la obtención de la subsecuencia máxima usa un tiempo lineal para calcular la suma de la mayor secuencia que atraviesa el borde, y después hace dos llamadas recursivas. Las llamadas recursivas calculan una suma que atraviesa el borde central, después hace más llamadas recursivas y así sucesivamente. El trabajo total invertido por el algoritmo es entonces proporcional al coste de las búsquedas recursivas.



/**Algoritmo de obtención de la subsecuencia de suma máxima. Encuentra la suma máxima de un subvector a [ izdo...dcho] no intenta mantener la mejor subsecuencia**/

private static int maxSumRec( int [] a, int izdo, int dcho)

{

    int maxSumIzdaBorde = 0;
    int maxSumDchaBorde = 0;
    int sumIzdaBorde = 0;
    int sumDchaBorde = 0;
    int centro = (izdo + dcho) / 2;
   
    if (izdo == dcho) //Hablamos del caso base
      return a  [izdo ] > 0 ? a[izdo]: 0;

     int maxSumIzda = maxSumRec ( a, izdo, centro);
     int maxSumDcha = maxSumRec (a, centro+1, dcho);

     for (int i=centro; i>=izdo; i--)
     {
        sumIzdaBorde += a[ i ];
        if( sumIzdaBorde > maxSumIzdaBorde)
            maxSumIzdaBorde = sumIzdaBorde;
      }


       for (int j=centro+1; j <= dcho; j++)
        {
           sumDchaBorde += a[ i ];
           if( sumDchaBorde > maxSumDchaBorde)
               maxSumDchaBorde = sumDchaBorde;
         }
 

       return max3 (maxSumIzda, maxSumDcha, maxSumIzdaBorde +  maxSumDchaBorde );

}

//Rutina visible pública

public static int maxSubSum4 ( int a  [ ] )

{
   return maxSumRec (a, 0, a.length-1);

}




La rutina max3 devuelve la mayor de las tres soluciones parciales, es decir, le pasamos tres números y devuelve el mayor.

Espero que el código no contenta errores, que lo he copiado a mano del libro.

ByEs [buenazo]
¡Muchas gracias por el esfuerzo, bitman! Unicamente habia un ligero error, y es que en el segundo bucle for que propones, accedes a [i], que es una variabe local del primer bucle for. Con cambiarlo por una j funcionaba.

Pero tengo un problema, ¡y es que ese algoritmo es NLogN! Es exactamente el que yo tenia planteado jajaja Supongo que igual si introduzco un vector que se vaya modificando, o algun tipo de memoria, podre rebajarlo a N, pero no soy capaz de sacar el como. Asi que sigo como al principio :P

De todas maneras, gracias otra vez, por el esfuerzo de buscar y copiarlo. ¡Con haberme dado la referencia del libro ya me hubieses hecho padre!

Si algun otro alma caritativa se apiada de mi....estare agradecidisimo XD. Un saludo.
He estado buscando un poquito, y he encontrado quizás una posible solución. Aquí dice lo siguiente:

El procedimiento Sumamax3(en este caso el que te dí antes) es de complejidad O(nlogn), puesto que su tiempo
de ejecución T(n) viene dado por la ecuación en recurrencia
T(n) = 2T(n/2) + An
con la condición inicial T(1) = 7, siendo A una constante.
Obsérvese además que este análisis es válido puesto que hemos añadido la
palabra VAR al vector a en la definición del procedimiento. Si no, se producirían
copias de a en las invocaciones recursivas, lo que incrementaría el tiempo de
ejecución del procedimiento.
Respecto a la última parte del problema, necesitamos encontrar un algoritmo
aún mejor que éste. La clave va a consistir en una modificación a la idea básica del
algoritmo anterior, basada en un algoritmo del tipo “en línea” (véase el problema
del elemento mayoritario, en este capítulo).
Supongamos que ya tenemos la solución del problema para el subvector
a[prim..i–1]. ¿Cómo podemos extender esa solución para encontrar la solución de
a[prim..i]? De forma análoga al razonamiento que hicimos para el algoritmo
anterior, la subsecuencia de suma máxima de a[prim..i] puede encontrarse en
a[prim..i–1], o bien contener al elemento a[i].
Esto da lugar a la siguiente función...


Está en la página 35-36. Habla de una posible función lineal aunque dice que no es fácil de entender, la verdad es que a simple vista no lo parece. Échale un vistazo y me cuentas.

ByEs [buenazo]
¡Gracias! Jejeje, pero la funcion "enlinea" (que tambien saque) no es divide y venceras, porque la implementacion natural de una funcion inline es un bucle for.

Finalmente lo conseguimos con un algoritmo bastante rarito, el libro de Narciso Marti "Estructura de datos y algoritmos" nos dio una idea XD. Por si a alguien le pica la curiosidad y no tiene acceso directo a esa publicacion, dejo la idea:
Se trata de acceder, de forma recursiva, a cada uno de los elementos del vector. Sobre cada vector, hay que llamar de forma recursiva a la mitad izquierda y mitad derecha, y una vez se vuelva de la llamada, recalcular el maximo actual, maximo empezando por la izquierda, maximo empezando por la derecha y suma total del vector.
Es un poco lio pero haciendolo en POO, te creas una estructura de datos para los maximos y luego el main se basa en hacer las dos recursiones y 4 o 5 comparaciones. Pero puedo asegurar que el algoritmo no es NADA evidente, desde luego, jejeje.

Muchisimas gracias por todas las molestias, bitman, de verdad.

Un saludo.
4 respuestas
Archivado
Volver a General