在Python中的Kadane算法|极客笔记

在Python中的Kadane算法

在下面，我们将讨论Kadane算法及其解决“最大子数组和”问题的特性。我们将理解该算法的概念，并使用Python代码进行相同的工作，同时提供示例及其相应的输出。最后，我们将讨论该算法的时间复杂度和Kadane算法的实际应用。

因此，让我们开始吧。

理解Kadane算法

Kadane算法是用于借助动态规划来解决问题的流行方法之一。正如我们所知，最大子数组问题被认为是动态规划领域中的热门问题之一。我们可能会认为这个问题看起来很简单，问题的输出将是数组中所有数据元素的总和。然而，这似乎是不正确的。我们还将遇到数组中作为数据元素的负整数，可能会减少整个数组的总和。因此，我们将借助Kadane算法来解决这个问题。

Kadane算法用于在一维整数数组中找到具有最大可能总和的连续子数组。在理解问题陈述之后，每个人的主要方法都将是应用蛮力算法来解决问题。然而，通过这样做，解决方案的时间复杂度将为O(n^2)，这是相当低效的。因此，我们将使用Kadane算法来解决该问题，通过遍历整个数组，并借助两个变量来跟踪到目前为止的总和和最大总和。在使用此算法时需要注意的最重要的方面是更新两个变量的条件。

理解最大子数组和的算法

现在让我们考虑最大子数组和算法的基本步骤，如下所示：

步骤1： 我们需要初始化 max_till_now = 0

步骤2： 我们需要初始化 max_ending = 0

步骤3： 我们需要对数组中的每个数据元素重复执行步骤 4 到 6。

步骤4： 我们需要设置 max_ending = max_ending + a[i]

步骤5： 如果 (max_ending < 0) ** 则我们需要设置 **max_ending = 0

步骤6： 如果 (max_till_now < max_ending) ** 则我们需要设置 **max_till_now = max_ending

步骤7： 我们需要返回 max_till_now

在上述算法的步骤中，我们使用了 max_ending 来查找数组中所有正数的数据元素，而 max_till_now 用来找到所有正数段中数据元素的最大总和。因此，每次在与 max_till_now 比较时得到正数总和，我们就能用更大的总和来更新它。

因此，每当 max_ending 变为负数时，我们将其置为零，并且在每次迭代时，我们将检查 max_till_now 小于 max_ending 的条件，以便在条件返回 True 时更新 max_till_now 。

使用图示表示理解Kadane算法

让我们考虑以下关于整数数组的示例。

在Python中的Kadane算法

图1： 整数数组

在Python中的Kadane算法

图2： 我们将初始化 max_till_now = 0 和 max_ending = 0（n = 0） 。

在Python中的Kadane算法

图3: 然后我们将得到 max_till_now = 0 和 max_ending = 0 ，对于 n = 1 ；然而，我们将得到 max_till_now = 4 和 max_ending = 4 ，对于 n = 2 。

在Python中的Kadane算法

图4： 我们将赋值 n = 3 和 4 ，并得到 max_till_now = 4 和 max_ending = 3 以及 max_till_now = 4 和 max_ending = 1 。

在Python中的Kadane算法

图 5： 我们将得到 max_till_now = 6 (6 > 4) ** 对于 **n = 5 和 max_ending = 6 。

在Python中的Kadane算法

图6： 我们还会得到 max_till_now = 6 和 max_ending = 4 对于 n = 6 。

因此，根据上面的示例，我们会找到从 n = 2 到 n = 5 的最大子数组，最大的和将是 6 。

使用Python代码理解Kadane的算法

让我们考虑以下演示Kadane算法工作原理的代码片段。

示例：

# defining the function to find the maximum subarray sum
def max_Subarray_Sum(my_array, array_size):
    # assigning the variables
    maxTillNow = my_array[0]
    maxEnding = 0

    # using the for-loop
    for n in range(0, array_size):
        maxEnding = maxEnding + my_array[n]
        # using the if-elif-else statement
        if maxEnding < 0:
            maxEnding = 0

        elif (maxTillNow < maxEnding):
            maxTillNow = maxEnding

    return maxTillNow
# defining the array
my_array = [-2, -3, 4, -1, -2, 5, -3]
# printing the maximum subarray sum for the users
print("Maximum Subarray Sum:", max_Subarray_Sum(my_array, len(my_array)))

输出：

Maximum Subarray Sum: 6

Explanation:

在上面的代码片段中，我们定义了一个函数 max_Subarray_Sum ，它接受两个参数 my_array 和 array_sum 。我们将变量 maxTillNow 赋值为数组的第一个索引值，将 maxEnding 赋值为零。然后我们使用 for循环 遍历整个数组。我们还使用 if-elif-else 条件语句并返回 maxTillNow 。最后，我们定义数组并打印用户的最大子数组和，即上面示例中的 6 。

时间复杂度

对于一个包含n个整数数据元素的数组，Kadane算法的时间复杂度被定义为 O(n) ，因为程序中只需执行一个for循环。同样，算法的辅助空间复杂度为 O(1) 。

应用场景

Kadane算法有多个应用，其中一些如下所述：

Kadane算法用于求解给定整数数组的最大子数组和。
它还被用作图像处理算法。
它也可以用于解决问题，如”按顺序旅行的车站”和”沿海的旅馆”。
它还被用于业务分析。

总结

最后，我们可以得出结论，当解决找到最大子数组和的问题陈述时，解决方案看起来并不容易和简单。然而，Kadane算法简化了解决此类问题，并在最小的时间复杂度下得出了解决方案。这是可能的，因为Kadane算法利用收集达到解决方案所需的信息的技术，避免了不必要的数据存储。因此，我们可以将这个算法看作是动态规划方法的一个简单示例，在现实世界中具有许多实际应用。