Máxima suma en un arreglo - dambort/algos GitHub Wiki

Problema: dado un arreglo V de n elementos, se desea saber cual es la máxima suma de números consecutivos.

Ejemplos:

1. Si V[ ] = {-1, 2, 4, -3, 5, 2, -5, 2}

   Salida: 10

2. Si V[ ] = {-1, 4, 2, -10, 7, 8, -1, -20}

   Salida: 15

Idea del algoritmo:

El algoritmo consiste en calcular, para cada posición del arreglo, la máxima suma del subarreglo que termina en esa posición. Luego, la solución es la máxima de estas sumas.

Código

Disponible en Enciclopedia Algoritmos C++

Ejemplo de uso

Disponible en ejemplo de suma maxima subarreglo

Complejidad: O(n), existen alternativas mas intuitivas pero con complejidades de tipo O(n²) y O(n³).

Fuente

Laaksonen, A. 2018, Competitive Programmer's Handbook.