我一直在解决 算法导论-CLRS中的 练习，并且遇到了在线性时间（问题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; }
除了将手动测试用例提供给程序外，是否有办法检查此算法的有效性？
这实际上取决于您对具有所有负值的数组的定义。
如果您不将空子数组视为可能的解决方案，那么可以，您的解决方案是正确的，并且实际上与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]。
sum
max
a[0]
但是，您再次在这里假设数组都不为空（在这种情况下，您将返回Integer.MIN_VALUE，是您想要的吗？），并且不可能有一个空子数组（sum == 0）。
Integer.MIN_VALUE
