最大连续子数组和的线性时间算法

Question

我一直在解决 算法导论 - CLRS 的练习，并遇到了在线性时间内解决最大连续子数组 (Q 4.1-5)。 请在下面查看我的解决方案。我一直在为这个练习寻找在线评委，但找到了 none。在我寻找解决方案解决它之后，我发现 kadane 的算法似乎与我的实现不同，而且当所有数字都是负数时，这个解决方案给出了正确的输出。

public static int linearMaxSolve(int[] arr) {
int max = Integer.MIN_VALUE;
int sum = 0;
for (int i : arr) {
    sum += i;
    if (i > sum) {
        sum = i;
    }
    if (sum > max) {
        max = sum;
    }
}
return max;
}

除了向程序提供手动测试用例之外，还有其他方法可以检查该算法的有效性吗？

Answer 1

这实际上取决于您对所有负值数组的定义。

如果您不将空 sub-array 算作可能的解决方案，那么是的，您的解决方案是正确的，实际上它与 Kadane's algorithm.

完全相同

int max_so_far = a[0];
int max_ending_here = a[0];

for (int i = 1; i < size; i++)
{
    max_ending_here = Math.max(a[i], max_ending_here+a[i]);
    max_so_far = Math.max(max_so_far, max_ending_here);
}
return max_so_far;

唯一的区别是初始化，但如果您仔细观察，在算法的第一次迭代中，sum 和 max 的值都将是 a[0].

但是，您再次假设您的数组不为空（在这种情况下您将 return Integer.MIN_VALUE，是您想要的吗？）并且一个空的 sub-array (sum==0) 不是一个可能的解决方案。