0

我一直在解决算法简介 - 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;
}

除了将手动测试用例输入程序之外，有没有办法检查这个算法的有效性？

4

1 回答 1

4

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

如果您不将空子数组视为可能的解决方案，那么是的，您的解决方案是正确的，实际上它与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）不是一个可能的解决方案。

于 2018-03-11T08:47:38.883 回答