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

maxSum([-1, -9, 0, 8, -76, 5, 3]) ➞ 8

maxSum([3, -10, 4, -1, 2, 3, 6, -7]) ➞ 14

maxSum([1, -9, 0, -8, 76, 5, 43]) ➞ 124

Observações

• Pode haver 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.