Par de sublistas com soma máxima (versão casual)

Este desafio é uma variante do problema clássico da sublista com soma máxima encontrado neste desafio.

Como o nome indica, dada uma lista de números, o objetivo desse problema é encontrar a sublista (ou seja, uma sequência de itens adjacentes) com a maior soma.

Por exemplo:

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

A sublista com soma máxima é [5, -1, 4], cuja soma é 5 - 1 + 4 = 8.

É importante observar que, neste desafio, permitimos sublistas vazias [], cuja soma é 0. Portanto, para uma lista [-4, -3, -5, -7] de números negativos, a sublista com soma máxima é [], com soma 0.

Este desafio trata do problema do par de sublistas com soma máxima, que é a variante do problema acima em que se escolhem duas sublistas com a maior soma total. Por exemplo, para a lista acima, o par de sublistas com soma máxima é o par [1, 6], [5, -1, 4], cuja soma total é 1 + 6 + 5 - 1 + 4 = 15.

Observe que, nessa variante, novamente permitimos que as sublistas sejam vazias. Por exemplo, 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.

Objetivo

Escreva uma função que, dada uma lista de números, retorne a soma total do par de sublistas com soma máxima.

Exemplos

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]

Observações

  • O clássico problema da sublista com soma máxima pode ser resolvido com eficiência usando o famoso algoritmo de Kadane, que executa em tempo linear O(n) (onde n é o comprimento da lista).
  • Portanto, como seria de esperar, o problema do par de sublistas com soma máxima também pode ser resolvido em tempo linear, mas o algoritmo é muito mais complicado. Neste desafio, todas as listas serão relativamente pequenas (no máximo 20 itens), portanto a eficiência não é necessária, e algoritmos ineficientes mais intuitivos passarão no desafio. Para a versão mais difícil deste desafio, na qual a eficiência é exigida, veja este desafio.