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
