Este desafio é uma versão mais difícil de um desafio anterior (que você deve resolver primeiro), que resolve o mesmo problema, mas com testes muito mais difíceis, que exigem que a solução seja bastante eficiente (veja as Notas abaixo).
O problema em questão é o par de sublistas com soma máxima, que, dada uma lista de números, tenta encontrar o par de sublistas com a maior soma combinada possível.
Por exemplo:
[1, 6, -1, -5, -2, 5, -1, 4, -7, 1, 2, 3]O par de sublistas com soma máxima é [1, 6], [5, -1, 4], cuja soma combinada é 1 + 6 + 5 - 1 + 4 = 15.
É importante observar que, neste desafio, permitimos sublistas vazias [], cuja soma é 0. Assim, para a lista:
[-1, -2, -3, 5, 4, 3, 4, 5, -9, -10]O par de sublistas com soma máxima é [5, 4, 3, 4, 5], [], com soma total de 5 + 4 + 3 + 4 + 5 = 21.
Escreva uma função eficiente que, dada uma lista de números, retorne a soma total do par de sublistas com soma 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]