Kadane 算法解释

Kadane 算法是一种用于解决最大子数组和问题的高效算法。该问题的目标是找到一个给定数组中具有最大和的连续子数组。Kadane 算法通过一次遍历数组，在 O(n) 时间复杂度内解决这个问题。以下是 Kadane 算法的详细解释：

原理

Kadane 算法基于动态规划的思想。它利用两个变量：

1. current_max：当前子数组的最大和。
2. global_max：全局子数组的最大和。

步骤

1. 初始化两个变量：
   • current_max 为数组的第一个元素。
   • global_max 也为数组的第一个元素。
2. 从数组的第二个元素开始，遍历数组。对于数组中的每一个元素，执行以下操作：
   • 将当前元素与 current_max + 当前元素 进行比较，选择较大的那个作为新的 current_max。也就是说，current_max = max(current_element, current_max + current_element)。
   • 更新 global_max，使其始终保持当前遇到的最大子数组和。也就是说，global_max = max(global_max, current_max)。
3. 遍历结束后，global_max 就是数组中具有最大和的子数组的和。

示例

考虑数组 [-2, 1, -3, 4, -1, 2, 1, -5, 4]，演示 Kadane 算法的执行过程：

1. 初始化：
   • current_max = -2
   • global_max = -2
2. 从第二个元素开始遍历：
   • 1：current_max = max(1, -2 + 1) = 1，global_max = max(-2, 1) = 1
   • -3：current_max = max(-3, 1 + -3) = -2，global_max = max(1, -2) = 1
   • 4：current_max = max(4, -2 + 4) = 4，global_max = max(1, 4) = 4
   • -1：current_max = max(-1, 4 + -1) = 3，global_max = max(4, 3) = 4
   • 2：current_max = max(2, 3 + 2) = 5，global_max = max(4, 5) = 5
   • 1：current_max = max(1, 5 + 1) = 6，global_max = max(5, 6) = 6
   • -5：current_max = max(-5, 6 + -5) = 1，global_max = max(6, 1) = 6
   • 4：current_max = max(4, 1 + 4) = 5，global_max = max(6, 5) = 6

最终，最大子数组和为 6，对应的子数组为 [4, -1, 2, 1]。

代码实现

以下是 Kadane 算法的 java 实现：

public class KadaneAlgorithm {

    // 实现 Kadane 算法的方法
    public static int kadaneAlgorithm(int[] arr) {
        int currentMax = arr[0];
        int globalMax = arr[0];

        for (int i = 1; i < arr.length; i++) {
            currentMax = Math.max(arr[i], currentMax + arr[i]);
            globalMax = Math.max(globalMax, currentMax);
        }

        return globalMax;
    }

    public static void main(String[] args) {
        // 示例数组
        int[] arr = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
        System.out.println("最大子数组和为: " + kadaneAlgorithm(arr));
    }
}

总结

Kadane 算法通过巧妙的动态规划思想，仅用一次遍历即可解决最大子数组和问题，具有线性时间复杂度，是处理这类问题的高效方法。