Arreglos, Encontrar la máxima suma de una submatriz consecutiva

Dada una lista de números positivos y negativos, encontrar la suma máxima de una matriz consecutiva.

¿Cómo funciona el algoritmo Kadane?

El algoritmo Kadane nos permite obtener la suma máxima de una matriz subyacente, este algoritmo es llamado así debido a al matemático Joseph Born Kadane.

¿Cuál es el pseudocódigo del algoritmo Kadane?

El pseudocódigo del algoritmo Kadane es el siguiente.

def kadane(A):
    max_current = maxglobal = A[0]
    for i from 1 to len(A) - 1:
        max_current = max(A[i], max_current + A[i])
    if max_current > max_global
        max_global = max_current
    return max_global

¿Cómo implementar el algoritmo Kadane en Go?

Ahora podemos integrar el algoritmo Kadane en Go.

// Creamos una funcion que obtenga el maximo entre dos
// valores enteros
func MaxInt(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func MaximaSumaConsecutiva(numeros []int) int {

	// definimos las variables suma y suma acumulada al
	// primer valor del arreglo
	maxCurrent := numeros[0]
	maxGlobal := numeros[0]

	// recorremos las entradas
	for i := 1; i < len(numeros); i++ {

		// comparamos la suma acumulada con la suma del acumulado
		// mas el valor actual y extraemos el mayor de ellos
		maxCurrent = MaxInt(numeros[i], numeros[i]+maxCurrent)

		// su el acumulado es mayor al global actualizamos
		// el global al valor del acumulado
		if maxCurrent > maxGlobal {
			maxGlobal = maxCurrent
		}
	}

	// returnamos el maximo global
	return int(maxGlobal)
}

Prueba.

func main() {
	data := []int{-2, 3, 2, -1}
	fmt.Println(MaximaSumaConsecutiva(data))
}

Salida.

5