Kadane算法

背景

Kadane算法（Kadane’s Algorithm）是一种用于解决最大子数组和问题（Maximum Subarray Sum Problem）的动态规划算法。该问题的目标是在给定整数数组中找到一个连续的子数组，使其元素之和最大。Kadane算法的时间复杂度为O(n)，其中n是数组的长度，因此它是解决这个问题的高效方法。

实现步骤

1. 初始化两个变量：currentMax（用于跟踪当前子数组的最大和）和globalMax（用于跟踪全局最大子数组的和）。初始值都可以设为数组的第一个元素。
2. 遍历数组中的每个元素，从第二个元素开始：

   a. 更新currentMax，将其设置为当前元素值与currentMax + 当前元素值中的较大者。这表示在当前位置考虑是否要继续扩展子数组，或者从当前位置重新开始一个新的子数组。

   b. 更新globalMax，将其设置为currentMax和globalMax中的较大者。这表示我们始终跟踪最大子数组的和。

3. 继续遍历数组的剩余元素，并重复步骤2。
4. 返回globalMax作为最大子数组的和。

代码实现

public class KadaneAlgorithm { public static int findMaxSubarraySum(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};
        int maxSum = findMaxSubarraySum(arr);
        System.out.println("最大子数组的和为: " + maxSum);
    }
}

如果数列中含有负数元素，并允许返回长度为零的子数列。我们可以对以上代码稍作修改，得到以下代码：

public class KadaneAlgorithmWithZeroLengthSubarray { public static int findMaxSubarraySum(int[] arr) { int currentMax = 0;
        int globalMax = 0;
        for (int i = 0; i < arr.length; i++) { currentMax = Math.max(0, 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};
        int maxSum = findMaxSubarraySum(arr);
        System.out.println("最大子数组的和为: " + maxSum);
    }
}