Par de sublistas con suma máxima (versión informal)

Este desafío es una variante del problema de la sublista con suma máxima clásico que se encuentra en este desafío.

Como indica el nombre y dada una lista de números, el objetivo de ese problema es encontrar la sublista (es decir, una secuencia de elementos adyacentes) con la suma más grande.

Por ejemplo:

[1, 6, -1, -5, -2, 5, -1, 4, -7, 1, 2, 3]

La sublista con suma máxima es [5, -1, 4], cuya suma es 5 - 1 + 4 = 8.

Cabe destacar que, en este desafío, permitimos sublistas vacías [], cuya suma es 0. Por lo tanto, para una lista [-4, -3, -5, -7] de números negativos, la sublista con suma máxima es [], con suma 0.

Este desafío trata el problema del par de sublistas con suma máxima, que es la variante del problema anterior en la que se eligen dos sublistas con la suma total máxima. Por ejemplo, para la lista anterior, el par de sublistas con suma máxima es el par [1, 6], [5, -1, 4], cuya suma total es 1 + 6 + 5 - 1 + 4 = 15.

Observa que, en esta variante, nuevamente permitimos que las sublistas estén vacías. Por ejemplo, para la lista:

[-1, -2, -3, 5, 4, 3, 4, 5, -9, -10]

El par de sublistas con suma máxima es [5, 4, 3, 4, 5], [], con una suma total de 5 + 4 + 3 + 4 + 5 = 21.

Objetivo

Escribe una función que, dada una lista de números, devuelva la suma total del par de sublistas con suma máxima.

Ejemplos

max_sum_pair([1, 6, -1, -5, -2, 5, -1, 4, -7, 1, 2, 3]) ➞ 15
# Max sum sublist pair is [1, 6], [5, -1, 4]

max_sum_pair([-1, -2, -3, 5, 4, 3, 4, 5, -9, -10]) ➞ 21
# Max sum sublist pair is [5, 4, 3, 4, 5], []

max_sum_pair([-4, 2, -3, -2, 2, -3, 5, -2]) ➞ 7
# Max sum sublist pair is [2], [5]

max_sum_pair([0, -1, 5, -6, 5, -3, 0, -4, 5, 2, -5, 1]) ➞ 12
# Max sum sublist pair is [5], [5, 2]

max_sum_pair([-5, 3, -4, 6, 0, 0, -4, -2, -2, 7, -5, 7, -5, 5]) ➞ 15
# Max sum sublist pair is [6], [7, -5, 7]

Notas

• El clásico problema de la sublista con suma máxima puede resolverse eficazmente mediante el famoso algoritmo de Kadane, que se ejecuta en tiempo lineal O(n) (donde n es la longitud de la lista).
• Por lo tanto, como era de esperar, el problema del par de sublistas con suma máxima también puede resolverse en tiempo lineal, pero el algoritmo es mucho más complicado. En este desafío, todas las listas serán relativamente pequeñas (20 elementos como máximo), así que la eficiencia no es necesaria y los algoritmos ineficientes más intuitivos superarán el desafío. Para la versión más difícil de este desafío, en la que se exige eficiencia, consulta este desafío.