Este desafío es una versión más difícil de un desafío anterior (que deberías resolver primero), que plantea el mismo problema, pero con pruebas mucho más difíciles que requieren que la solución sea bastante eficiente (consulta las Notas más abajo).
El problema en cuestión es el par de sublistas con suma máxima, que, dada una lista de números, intenta encontrar el par de sublistas con la mayor suma combinada posible.
Por ejemplo:
[1, 6, -1, -5, -2, 5, -1, 4, -7, 1, 2, 3]El par de sublistas con suma máxima es [1, 6], [5, -1, 4], cuya suma combinada es 1 + 6 + 5 - 1 + 4 = 15.
Es importante observar que, en este desafío, permitimos sublistas vacías [], cuya suma es 0. Por lo tanto, 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.
Escribe una función eficiente que, dada una lista de números, devuelva la suma total del par de sublistas con suma máxima.
[1, 6, -1, -5, -2, 5, -1, 4, -7, 1, 2, 3] ➞ 15
# Max sum sublist pair is [1, 6], [5, -1, 4]
[-1, -2, -3, 5, 4, 3, 4, 5, -9, -10] ➞ 21
# Max sum sublist pair is [5, 4, 3, 4, 5], []
[-4, 2, -3, -2, 2, -3, 5, -2] ➞ 7
# Max sum sublist pair is [2], [5]
[0, -1, 5, -6, 5, -3, 0, -4, 5, 2, -5, 1] ➞ 12
# Max sum sublist pair is [5], [5, 2]
[-5, 3, -4, 6, 0, 0, -4, -2, -2, 7, -5, 7, -5, 5] ➞ 15
# Max sum sublist pair is [6], [7, -5, 7]