Go 语言实现 Kadane 算法

---

有一个著名的最大子数组和问题，其中我们有一个一维数组，必须找到该子数组中的最大和。为了解决这个问题，最简单的办法是找到所有子数组，将它们的元素求和，并返回最大值，但时间复杂度将为 O(N*N)。为了减少这一点，有一种算法可以将时间复杂度从 O(N*N) 降低到 O(N)，称为 Kadane 算法。

在编程中，有一些基于动态规划概念的算法，其中问题被分解成子问题，并保存结果，用于类似的子问题。Kadane 算法也是动态规划算法之一，它将使用前一个索引存储到当前索引为止的最大子数组和。

算法

步骤 1：使用 import 关键字在顶部导入所需的包。

步骤 2：然后 main 函数将首先运行。

• 首先，我们声明并初始化数组。

• 现在我们正在调用 maxSumSubArray() 函数，在其中我们实现了 Kadane 算法。

步骤 3：maxSumSubArray() 函数实现

• 初始化名为 sum 和 maxSum 的变量，并分别初始化为 0 和 INT_MIN。

• 对数组的每个元素运行 for 循环。在每次迭代中

• 将当前索引值添加到变量 sum 中。

• 如果条件是检查 sum 是否大于 maxSum，如果是，则我们将 dp maxSum = sum。

• 另一个 if 条件是检查 sum 是否小于零，如果是，则使 sum = 0。

• 返回 maxSum 值。

步骤 4：打印给定数组中由 maxSumSubArray() 函数返回的最大子数组和。

示例

让我们找到数组 {3, −3, 4, 2, −1, 5} 的最大子数组和。

Sum = 0

maxSum = INT_MIN

迭代 1

At i = 0 array[i] = 3
Sum = 0 + 3
    = 3
maxSum < sum
maxSum = 3  

迭代 2

At i = 1 array[i] = −3
Sum = 3 + (−3)
    = 0
maxSum > sum
maxSum = 3

迭代 3

At i = 2 array[i] = 4
Sum = 0 + 4
    = 4
maxSum < sum
maxSum = 4

迭代 4

At i = 3 array[i] = 2
Sum = 4 + 2
    = 6
maxSum < sum
maxSum = 6

迭代 5

At i = 4 array[i] = −1
Sum = 6 + (−1)
    = 5
maxSum > sum
maxSum = 6

迭代 6

At i = 5 array[i] = 5
Sum = 5 + (5)
   = 10
maxSum < sum
maxSum = 10

示例

在以下示例中，我们将演示如何开发一个 Go 语言程序来实现 Kadane 算法。

package main

import (
    "fmt"
    "math"
)

// function to print the array with array and
// size of the array as argument
func printArray(array []int, size int) {
    for i := 0; i < size; i++ {
        fmt.Print(array[i], " ")
    }
    fmt.Println()
}

func maxSumSubArray(array []int, size int) int {
    // declaring variable sum of int type
    // and an iterator i
    var sum, maxSum, i int

    // initializing the variables declared above
    sum = 0
    maxSum = math.MinInt
    i = 0

    // running for loop from o to the size of the array
    for i < size {
        sum = sum + array[i]
        if sum > maxSum {
            maxSum = sum
        }
        if sum < 0 {
            sum = 0
        }
        i++
    }
    return maxSum
}

func main() {
    // declaring and initializing the
    // array of size 6 using the shorthand method
    array := []int{-2, -3, 4, -1, -2, 1, 5, -3}

    fmt.Println("Golang program to find the maximum sum subarray in the given array using Kaden's algorithm.")
    fmt.Print("array: ")
    printArray(array, len(array))

    // calling maxSumSubArray() function by passing array and length as a parameter
    sum := maxSumSubArray(array, len(array))

    fmt.Println("The maximum sum is", sum)
}

输出

Golang program to find the maximum sum subarray in the given array using Kaden's algorithm.
array: -2 -3 4 -1 -2 1 5 -3
The maximum sum is 7

结论

这是 Kadane 算法的实现，它是一种动态规划算法，用于查找最大子数组和。为了在最短的时间内解决面试中的此类问题，每个人都使用 Kadane 算法。要了解有关 Go 语言的更多信息，您可以浏览这些 教程。