Solução de Frederico Bulhões
Para resolver esse problema podemos usar um algoritmo conheciodo como algoritmo de Sublista Contígua de Soma Máxima, usando o algoritmo de Kadane.
Em resumo o algoritmo de Kadane calcula a maior soma terminando em cada posição do vetor, usando programação dinâmica, e por fim calcula o máximo desses máximos.
Código para melhor entendimento:
https://gist.github.com/fredbr/4e87f503be2fda44cf316babf4c4e9ae
Deixe um comentário