Algoritmos y Estructuras de Datos

Conquista la subarreglo de suma máxima con el algoritmo Divide & Conquer

Existen muchas maneras de encontrar la subarreglo de suma máxima para n enteros. Una forma de resolver este problema es con el algoritmo de divide & conquer. Para hacerlo, se divide el arreglo recursivamente en 2 partes; luego se encuentra la subarreglo de suma máxima en la parte izquierda, en la parte derecha y en la parte que cruza el punto medio. Al final, se calcula la respuesta para el arreglo actual a partir de esos resultados.
El pseudocódigo para el algoritmo podría ser:
def max_subarray(a):
    # Casos base
    if len(a) == 0:
        return float('-inf'), float('-inf'), float('-inf')
    if len(a) == 1:
        return a[0], a[0], a[0]

    # Divide (obtén respuestas para las partes izquierda y derecha)
    ll, lmax, lr = max_subarray(a[:len(a) // 2])
    rl, rmax, rr = max_subarray(a[len(a) // 2:])
    lsum = sum(a[:len(a) // 2])
    rsum = sum(a[len(a) // 2:])

    # Obtiene 3 números y retorna el prefijo máximo, el sufijo máximo y la suma máxima total
    return conquer(ll, lmax, lr, lsum, rl, rmax, rr, rsum)
En este problema, se te pide implementar la parte de la función conquer, donde, dados 8 números, debes encontrar correctamente 3 valores que representen: la mejor suma de prefijo (best prefix sum), la mejor suma que cruza el punto medio (best cross sum) y la mejor suma de sufijo (best suffix sum). Los 8 números que se reciben son:
  1. La mejor suma de prefijo de la subarreglo izquierda
  1. La suma máxima de la subarreglo izquierda
  1. La mejor suma de sufijo de la subarreglo izquierda
  1. La suma de todos los números en la subarreglo izquierda
  1. La mejor suma de prefijo de la subarreglo derecha
  1. La suma máxima de la subarreglo derecha
  1. La mejor suma de sufijo de la subarreglo derecha
  1. La suma de todos los números en la subarreglo derecha

Entrada

La única línea de la entrada contiene 8 enteros en el orden descrito anteriormente. Todos los enteros no exceden en valor absoluto.

Salida

El programa debe imprimir 3 números: la mejor suma de prefijo, la mejor suma que cruza el punto medio y la mejor suma de sufijo.

Ejemplos

Input
Output
7 13 9 6 7 9 3 -2
13 16 7
7 13 9 6 5 25 3 1
11 25 10
 

Constraints

Time limit: 2 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue