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

Question

我一直在解决算法简介 - CLRS中的练习，并遇到了在线性时间内求解最大连续子数组的问题（Q 4.1-5）。请看下面我的解决方案。我一直在网上寻找这项练习的评委，但没有找到。解决这个问题后，当我寻找解决方案时，我发现 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

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

如果您不将空子数组视为可能的解决方案，那么是的，您的解决方案是正确的，实际上它与 Kadane算法完全相同。

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]。

但同样，您在这里假设您的数组不为空（在这种情况下您将返回Integer.MIN_VALUE，这是您想要的吗？）并且空子数组（sum==0）不是可能的解决方案。