Java 中的 Kadane 算法

最大子数组问题是算法问题中可以通过Kadane 算法解决的高效算法之一。这里的问题是找到连续子数组的最大和，可以在一维数组中以 O(n) 的时间复杂度解决。

该算法在商业和金融等领域非常有用，因为它可用于推断最有利可图的交易日，或在深入的分析领域识别更高活动模式。它的适用性不仅限于常规的算法问题，还可以应用于任何其他可以使用子数组或序列解决的动态规划问题。

Kadane 算法 简单地一次性计算出 jusqu'à dernier élément 的最大子数组和，这意味着要么继续将当前元素添加到之前的子数组中，要么在当前元素能产生更好的结果时以该元素开始新的子数组。

这种方法在空间和时间方面同样高效有效，并且使用简单的逻辑推理来解决看似复杂的问题；这就是为什么 Kadane 算法是高效数据分析和动态规划的重要工具。

问题陈述

最大子数组问题的动机是确定给定数组的哪个连续子数组产生的和最大。例如，给定 数组

我们将跟踪最大和及其子数组的边界，该子数组为 [4, −1, 2, 1]，最大和为 6。这个问题可以使用 Kadane 算法以 O(n) 的时间复杂度解决，这使得该过程效率很高。

算法直觉

我认为 Kadane 算法围绕的最基本思想是“滑动窗口”的概念。该算法在维护两个 变量的同时检查数组中的每个元素

• currentSum 帮助跟踪数组元素的总和，直到到达给定数组左侧的子数组。
• 至今遇到的最大和 (maxSum) - 此变量存储直到现在为止已验证的最大和。

它从数组的每个元素开始移动，通过将当前数组元素添加到 currentSum 中来扩展它，或者以当前元素开始一个新的子数组。如果 currentSum 超过 maxSum，则 maxSum 的值将被 current Sum 覆盖。

Kadane 算法的步骤

Kadane 算法本质上是在每个元素上决定是

• 将元素添加到 current Sum 并继续当前子数组。
• 从当前数字开始一个新的子数组。

通过执行以上两个步骤并记录全局最大值，就可以确保算法能够为任何给定的连续子数组情况产生最大和。现在，让我们仔细研究该算法，以便更清楚地理解其中涉及的数学过程。

文件名：KadaneAlgorithm.java

输出

 
Maximum subarray sum is: 6   

复杂度分析

时间复杂度： O(n)，因为实现的每个函数都需要与输入数组大小成比例的操作次数。

空间复杂度： O(1)，因为我们需要常量量的额外空间来存储 maxsum 和 currentsum。

结论

Kadane 算法是最大子数组问题的另一个最优解决方案。它利用了运行总和的概念，即每个元素的总和，同时动态地选择最佳选择，是将其添加到当前子数组的总和中。

如果初始化一个新的子数组更明智，因为当前元素小于之前的元素，具体取决于哪种选择会产生最大的总体和值。

因此，所提出的方法具有 O(n) 的时间复杂度和 O(1) 的空间复杂度，当处理大量数据时，这必须是该问题的最佳解决方案。学习 Kadane 算法是 动态规划 和解决连续子数组类型子问题的良好开端。