连续子数组最大和 (Kadane 算法)

您准备好进入算法的殿堂了吗？在这里，简单与强大相结合，看似复杂问题的答案就在眼前！在计算机科学和数据分析领域，寻找整数连续子数组中的最大和是一个常见问题。这项任务，就像在众多披萨中寻找最合适的那一片一样，可能看起来很困难，但别担心！我们将揭开 Kadane 算法的秘密，这是一种奇妙的方法，它不仅简化了问题，而且以优雅且高效的方式解决了它。加入我们，深入了解 Kadane 算法的魅力，看看它是如何改变我们处理连续子数组问题的。

Kadane 算法方法

Kadane 算法是连续子数组问题领域的真正变革者，它以优雅和高效的方式运行。要理解它，请想象一个包含正数和负数的数组，任务是找到具有最大和的连续子数组。这就像在各种大小和口味的披萨中寻找最美味的一片。

Kadane 算法的优点在于其简单性。它跟踪两个关键变量：max_ending_here（在此处结束的最大值）和 max_so_far（迄今为止的最大值）。这些变量是我们遍历数组的向导，帮助我们高效地识别最大和。以下是它的工作原理：

1. 初始化：我们首先将 max_ending_here 和 max_so_far 设置为数组中第一个元素的值。此步骤确保我们有一个参考点。
2. 迭代：当我们遍历数组时，对于每个元素，我们都会重复执行两个关键操作：
   • 更新 max_ending_here：在每一步，我们决定是开始一个新的子数组更有利，还是继续当前的子数组。我们通过比较当前元素的值与当前元素和 max_ending_here 的总和来实现这一点。哪个更大，哪个就成为新的 max_ending_here。
   • 更新 max_so_far：同时，我们将 max_so_far 与 max_ending_here 进行比较，并选择两者中较大的一个。此步骤确保 max_so_far 在迭代过程中始终保持迄今为止遇到的最大和。
3. 继续：我们对数组中的每个元素重复这些操作，让 max_so_far 演变并捕获任何连续子数组的最大和。

通过遵循这些简单的步骤，Kadane 算法确保我们在旅程的每一点都做出最佳选择，无论它是重新开始还是继续当前的子数组。这种动态规划方法即使在处理相当大的数组时也能保证效率和有效性。

示例

输入数组 [-2, 1, -3, 4, -1, 2, 1, -5, 4]

我们想使用 Kadane 算法找到具有最大和的连续子数组。让我们逐步进行：

1. 初始化：我们首先初始化两个变量：
   • max_ending_here 设置为第一个元素的值，即 -2。
   • max_so_far 也设置为 -2，因为它代表迄今为止遇到的最大和。
2. 迭代：现在，我们遍历数组，一次考虑一个元素：
   • 在索引 1 处（值：1）
     • 我们将当前元素 1 与当前元素和 max_ending_here 的总和（-2 + 1 = -1）进行比较。由于 1 大于 -1，我们将 max_ending_here 更新为 1。
     • 由于它现在大于前一个值，我们还更新了 max_so_far，使其变为 1。
   • 在索引 2 处（值：-3）
     • 我们将 -3 与 -3 和 max_ending_here 的总和（1 - 3 = -2）进行比较。在这种情况下，-2 大于 -3，因此 max_ending_here 保持为 1。
     • max_so_far 没有改变，因为 -2 不大于 1。
   • 在索引 3 处（值：4）
     • 我们将 4 与 4 和 max_ending_here 的总和（1 + 4 = 5）进行比较。5 大于 4，因此 max_ending_here 更新为 5。
     • max_so_far 被更新为 5，因为它现在大于前一个值。
   • 继续对剩余元素执行此过程：
     • 在索引 4 处（值：-1），max_ending_here 保持为 5，max_so_far 保持为 5。
     • 在索引 5 处（值：2），max_ending_here 变为 7（2 + 5），max_so_far 更新为 7。
     • 在索引 6 处（值：1），max_ending_here 变为 8（1 + 7），max_so_far 更新为 8。
     • 在索引 7 处（值：-5），max_ending_here 变为 3（-5 + 8），max_so_far 保持为 8。
     • 最后，在索引 8 处（值：4），max_ending_here 变为 7（4 + 3），max_so_far 更新为 8。
3. 结论：遍历完整个数组后，我们就得到了结果。max_so_far 保存了连续子数组的最大和，在本例中为 8。

因此，使用 Kadane 算法，我们有效地在连续子数组 [4, -1, 2, 1] 中找到了最大和（8）。这展示了 Kadane 算法在解决此类问题方面的强大功能和简单性。它动态地调整其变量，以确保在每一步都做出最佳选择，使其成为程序员工具包中的宝贵工具。

Python 实现

方法 1。

输出

Maximum contiguous sum is 7

1. 函数 find_max_contiguous_subarray_sum 接受一个数组 arr 作为输入，并返回连续子数组的最大和。
2. 将 max_sum_so_far 初始化为负无穷，将 current_max_sum 初始化为 0。这些变量将分别跟踪迄今为止遇到的最大和以及当前运行的总和。
3. 循环遍历输入数组的元素。
4. 对于数组中的每个元素 num：
   • 将 num 添加到 current_max_sum 以更新运行总和。
5. 检查 max_sum_so_far 是否小于 current_max_sum。如果是，则将 max_sum_so_far 更新为 current_max_sum。
6. 如果 current_max_sum 变为负数（表示当前子数组对总和的贡献为负），则将 current_max_sum 重置为 0。
7. 循环遍历所有元素后，max_sum_so_far 保存了连续子数组的最大和。
8. 最后，打印结果，即最大的连续和。

方法 2。

输出

Maximum contiguous sum is 7

1. 导入 sys 库
   程序首先导入 sys 库。sys 库提供对某些系统特定参数和函数的访问，包括常量 sys.maxsize，它用作需要表示负无穷大的变量的初始值。在这种情况下，它用于将 left_sum 和 right_sum 初始化为负无穷。
2. 定义递归函数
   程序定义了一个名为 find_largest_contiguous_sum 的函数，该函数以数组（arr）作为输入。
3. 基本情况
   • 如果输入数组（arr）的长度为 1（即它只包含一个元素），它将返回该元素，因为它代表了可能的最大和（只有一个元素）。
4. 递归情况
   • 当输入数组包含多个元素时，程序将进入递归情况。
5. 查找中间元素
   • 它计算数组（arr）中中间元素（middle）的索引。
6. 递归调用
   • 程序进行两次递归调用：
     • 一次用于数组的左半部分（arr[:middle]）以找到 left_max。
     • 另一次用于数组的右半部分（arr[middle:]）以找到 right_max。
7. 查找最大跨子数组和
   • 程序将变量 left_sum 和 right_sum 初始化为负无穷。这些变量将用于跟踪从中间元素向左和向右的子数组的和。
   • 它还将 current_sum 初始化为 0，用于计算子数组的和。
   • 程序然后从中间向右遍历数组：
     • 它将每个元素添加到 current_sum。
     • 将 right_sum 更新为当前值和 current_max_sum 中的较大者。
   • 在此之后，它将 current_sum 重置为 0，并从中间向左遍历数组，同样更新 left_sum。
   • cross_max 计算为在中间元素处相交的左侧和右侧子数组的和。
8. 返回最大值
   • 程序返回三个值中的最大值：cross_max、left_max 和 right_max。这代表当前子数组的最大连续子数组和。