Golang 实现Kaden算法

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

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

步骤

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

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

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

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

步骤3： maxSumSubArray()函数的实现

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

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

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

  • 检查条件是否sum大于maxSum，如果是，则更新maxSum = sum。

  • 另一个条件是检查sum是否小于零，如果是，则将sum设置为0。

• 返回maxSum的值。

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

示例

让我们找出数组{3, -3, 4, 2, -1, 5}的最大子数组和

和 = 0

最大和 = 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

示例

在下面的示例中，我们将演示如何开发一个使用Kaden算法的Golang程序

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

结论

这是Kaden算法的实现，它是一种动态规划算法，用于找到最大和的子数组。在面试中解决这类问题时，为了以最少的时间使用Kaden算法，每个人都会使用Kaden算法。要了解更多关于Golang的信息，您可以探索这些教程。