最大连续子数组和的线性时间算法 [英] Linear time algorithm for Maximum contiguous sub-array sum

问题描述

我一直在解决从算法简介到CLRS 的练习，并且遇到了在线性时间内求解最大连续子数组的问题(问题4.1-5). 请在下面查看我的解决方案.我一直在寻找此练习的在线法官，但没有找到.在寻找解决方案时解决了这一问题，我发现kadane的算法似乎与我的实现不同，当所有数字均为负数时，该解决方案也能提供正确的输出.

I have been solving exercise from Introduction to Algorithms - CLRS and came across solving maximum contiguous sub-array in linear time (Q 4.1-5). Please look at my solution below. I have been searching for online judges for this exercise but found none. After solving it when I looked for solutions I found kadane's algorithm which seems different than my implementation also this solution gives the correct output when all numbers are negative.

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;
}

除了将人工测试用例提供给程序外，是否有办法检查该算法的有效性?

Is there a way to check the validity of this algorithm apart from feeding in manual test cases to the program?

推荐答案

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

This really depends on what is your definition for an array with all negative values.

如果您不将空子数组视为可能的解决方案，那么可以，您的解决方案是正确的，实际上与

In case you don't count the empty sub-array as a possible solution then yes, your solution is correct and actually it's exactly the same as the 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].

The only difference is the initialization, but if you'll take a closer look, at the first iteration of your algorithm, both sum and max will have the value of a[0].

但是，您再次在这里假设两个数组都不为空(在这种情况下，您将返回Integer.MIN_VALUE，这是您想要的吗?)，并且一个空子数组(sum == 0)是不可能的解决方案.

But again, you assume here that both your array isn't empty (in that case you'll return Integer.MIN_VALUE, is that what you want?) and that an empty sub-array (sum==0) is not a possible solution.

这篇关于最大连续子数组和的线性时间算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！