Soma máxima

É fornecida uma sequência de inteiros. Sua tarefa é escolher um trecho contínuo dessa sequência de modo que a soma dos seus elementos seja maximizada. Você só precisa retornar a maior soma obtida.

Por exemplo, suponha que você receba a sequência (3, -10, 4, -1, 2, 3, 6, -7). Você obtém a maior soma escolhendo os elementos (4, -1, 2, 3, 6), cuja soma é 14.

Exemplos

max_sum((-1, -9, 0, 8, -76, 5, 3)) ➞ 8

max_sum((3, -10, 4, -1, 2, 3, 6, -7)) ➞ 14

max_sum((1, -9, 0, -8, 76, 5, 43)) ➞ 124

Observações

• Há até 10,000 inteiros em cada sequência.
• É possível escolher um trecho com zero elementos. Nesse caso, a soma é 0.
• Este desafio pode ser resolvido em tempo linear e espaço constante.