## Divide y vencerás

Este es un método de diseño de algoritmos que se basa en *subdividir* el problema en sub-problemas, resolverlos *recursivamente*, y luego *combinar* las soluciones de los sub-problemas para construir la solución del problema original. Es necesario que los subproblemas tengan la misma estructura que el problema original, de modo que se pueda aplicar la recursividad.

## Ejemplo: Obtener la subsecuencia de suma máxima

Dada una sucesión de enteros $$ a_{1}, a_{2}, …, a_{n}$$

encontrar e identificar el valor máximo de la suma de una porción consecutiva de la secuencia. 

Cuando todos los enteros son negativos entendemos que la subsecuencia de suma máxima es la vacía, siendo su suma cero.

Ejemplos: 

1. { -2, 11, -4, 13, -5, 2}
2. {1, -3, 4, -2, -1, 6}

Si revisamos el problema de forma intuitiva, mediante el uso de esquemas por ejemplo, para 1 y 2 las subsecuencias de suma máxima están marcadas en negrita:

1. { -2, **11, -4, 13**, -5, 2}

    y la suma de esta es 20.

2. {1, -3, **4, -2, -1, 6**}

    y la suma de esta es 7.


Esta solución intuitiva utiliza del orden de $n^2$ comparaciones: $\Theta(n^2)$.

## Usando divide y vencerás

Supongamos ahora que la sucesión dada es {4, -3, 5, -2, -1, 2, 6, -2}. Dividiremos esta secuencia en dos partes iguales, como se muestra en la figura a continuación.




Entonces la subsecuencia de suma máxima puede aparecer en una de estas tres formas:

*   *Caso 1*: está totalmente incluida en la primera mitad.
*   *Caso 2*: está totalmente incluida en la segunda mitad.
*   *Caso 3*: comienza en la primera mitad, pero termina en la segunda.


La figura anterior muestra que podemos calcular, para cada elemento de la primera mitad, la suma de la subsecuencia contigua que termina en el elemento situado más a la derecha. Hacemos esto con un recorrido de derecha a izquierda, partiendo del elemento situado entre las dos mitades. Análogamente, podemos calcular la suma de todas las subsecuencias contiguas que comiencen con el primer elemento de la segunda mitad. Entonces se puede combinar estas dos subsecuencias para formar la subsecuencia de suma máxima que cruza la línea divisoria. En el ejemplo de la figura, la secuencia resultante va desde el primer elemento de la primera mitad hasta el penúltimo elemento de la segunda mitad. La suma total es la suma de las dos subsecuencias, 4+7 = 11. Esto nos muestra que el caso 3 se puede resolver en tiempo lineal.

Tanto para el caso 1 como el caso 2, tenemos el mismo problema original, pero para una secuencia de tamaño $n/2$, es decir el mismo $\Theta(n^2)$ (recordemos que se obvían los coeficientes).

Sin embargo, podemos aplicar la misma estrategia de división por la mitad en los casos 1 y 2. Podemos continuar dividiendo hasta que sea imposible dividir más. Esto equivale, más concretamente, a resolver los casos 1 y 2 recursivamente. Se puede demostrar que esto reduce el tiempo de ejecución por de bajo de cuadrático, pues los ahorros se acumulan a lo largo de la ejecución del algoritmo. Mostramos a continuación un esquema del algoritmo:

1.   Calcular recursivamente la subsecuencia de suma máxima que está totalmente contenida en la primera mitad. 

2.   Calcular recursivamente la subsecuencia de suma máxima que está totalmente contenida en la segunda mitad.

3.   Calcular, usando dos bucles consecutivos, la subsecuencia de suma máxima que comienza en la primera mitad pero termina en la segunda. 

4.   Elegir la mayor de las tres sumas.

El método resultante aparece a continuación. Un algoritmo recursivo nos exige definir un caso base. Naturalmente, cuando el dato es un solo elemento, no usamos recursión.

A la llamada recursiva se le pasa el vector de entrada junto con los límites izquierdo y derecho, los cuales delimitan la porción de vector sobre la que se está operando. Una rutina guía de una línea inicializa los parámetros límite a 0 y N - 1.



```python
def max3(a,b,c):
  aux=[]
  aux.append(a)
  aux.append(b)
  aux.append(c)

  max = -1000
  for e in aux:
    if e > max:
      max = e
  
  return max

def maxSumaRec( a, izq, der): # Sub-problema cualquiera
                              # a: [][   ][   ] | [][][]. (n=6)
                              #       izq  der
                              # 
                              # Sub-problema inicial
                              # a: [   ][   ][        ] | [][][    ]
                              #    izq=0.     centro=2.        der=5
  maxSumIzqBorde = 0; maxSumDerBorde = 0
  sumIzqBorde = 0; sumDerBorde = 0

  centro = int((izq+der)/2)

  # CASO BASE:

  if izq == der:
    if a[izq] > 0:
      return a[izq]
    else:
      return 0

  # Se busca de forma recursiva la suma máxima en la sección izquierda
  maxSumIzq = maxSumaRec(a, izq, centro)

  # Se busca de forma recursiva la suma máxima en la sección derecha
  maxSumDer = maxSumaRec(a, centro+1, der)


  for i in range(centro, izq-1,-1): # al ppio: 3, 2, 1, 0 , para el ej.
    sumIzqBorde += a[i]
    if sumIzqBorde > maxSumIzqBorde:
      maxSumIzqBorde = sumIzqBorde
  
  for j in range(centro+1, der+1): # al ppio: 4, 5, 6, 7
    sumDerBorde += a[j]
    if sumDerBorde > maxSumDerBorde:
      maxSumDerBorde = sumDerBorde

  return max3(maxSumIzq,maxSumDer, maxSumIzqBorde+maxSumDerBorde)

a = [4,-3,5,-2,-1,2,6,-2]
print(maxSumaRec(a,0,len(a)-1))

b = [-2, 11, -4, 13, -5, 2]
print(maxSumaRec(b,0,len(b)-1))

c = [1, -3, 4, -2, -1, 6]
print(maxSumaRec(c,0,len(c)-1))

```

    11
    20
    7


### Ejercicio de divide y vencerás

Si tenemos dos números complejos

$$
\begin{align}
u&=a+bi\\
v&=c+di
\end{align}
$$

podemos calcular su producto

$$
uv=(ac-bd)+(ad+bc)i
$$

haciendo 4 multiplicación de números reales.

Encuentre una forma de realizar este cálculo haciendo solo 3 multiplicaciones de números reales.

## Referencias

1. Weiss, M. A., & Marroquín, O. (2000). Estructuras de datos en JavaTM. Addison-Wesley.

2. Apuntes de Patricio Poblete (U. de Chile) disponible en: https://github.com/ivansipiran/AED-Apuntes#Algoritmos-y-Estructuras-de-Datos (visitado en mayo 2021)

c580d718bf76158a572568de2acf9a892e6899af
ipynb
Jupyter Notebook
Dividir_para_reinar.ipynb
femunoz/AED
7d156a385ff4e4948f53003eb161ff2df0088bb2
CC0-1.0
2022-01-16T16:15:34.000Z
2022-01-16T16:15:34.000Z
Dividir_para_reinar.ipynb
femunoz/AED
7d156a385ff4e4948f53003eb161ff2df0088bb2
CC0-1.0
Dividir_para_reinar.ipynb
femunoz/AED
7d156a385ff4e4948f53003eb161ff2df0088bb2
CC0-1.0
Qwen/Qwen-72B
1. YES
2. YES