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 算法

让我们来看一个整数数组的示例如下。

图 1： 整数数组

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

图 3： 然后我们得到 n = 1 时的 max_till_now = 0 和 max_ending = 0；然而，我们得到 n = 2 时的 max_till_now = 4 和 max_ending = 4。

图 4： 然后我们将 n = 3 和 4 的值赋给，分别得到 max_till_now = 4 和 max_ending = 3，以及 max_till_now = 4 和 max_ending = 1。

图 5： 我们得到 n = 5 时的 max_till_now = 6 (6 > 4) 和 max_ending = 6。

图 6： 我们还得到 n = 6 时的 max_till_now = 6 和 max_ending = 4。

因此，从上面的例子中，我们将找到从 n = 2 到 n = 5 的最大子数组，最大和为 6。

通过 Python 代码理解 Kadane 算法

让我们看下面的代码片段，演示 Kadane 算法的工作原理。

示例

输出

Maximum Subarray Sum: 6

说明

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

理解时间复杂度

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

理解应用

Kadane 算法有各种应用，其中一些描述如下

1. Kadane 算法用于查找给定整数数组的最大子数组和。
2. 它被用作图像处理的算法。
3. 它还可以用于解决“有序站点旅行”和“海岸沿线旅馆”等问题。
4. 它也用于商业分析。

结论

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