🥇 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