最大和子数组O(n)not Kadane

Question

现在我用不同的测试场景测试它，总是比Kadena的结果更好。我不相信这样的运气，但找不到我错过了什么。你能看看这是否是一个有效的解决方案吗？

public void findMaxSubarray(Number[] numbers) {
    int maxSum = Integer.MIN_VALUE;
    int left = 0;
    int right = numbers.length - 1;

    int i = 0;
    int j = i + 1;
    int sum = numbers[i].intValue();

    while (i < numbers.length) {
        if (maxSum < sum) {
            maxSum = sum;
            left = i;
            right = j - 1;
        }
        if (j >= numbers.length)
            return;
        sum = sum + numbers[j].intValue();
        if (sum <= 0) {
            // ignoring "first" negative numbers. shift i to first non-negative
            while (numbers[j].intValue() <= 0) {
                if (maxSum < numbers[j].intValue()) {
                    maxSum = numbers[j].intValue();
                    left = j;
                    right = j;
                }
                if (++j >= numbers.length)
                    return;
            }
            i = ++j;
            sum = 0;
        }
        j++;
    }
    System.out.println(String.format("Max subarray is %d, [%d; %d]", maxSum, left, right));
}

更新代码的思想是只跟踪一个子数组，并添加到其尾数，当数字很低时，和成为尾数组后的负集开始。另外，一开始的负面项目被忽略了。子数组的头只是向前移动。每次sum看起来是maximal-maxsum并且限制被更新。

shift i() --to first non negative number
from j = i+1 up to N.length
  sum + N[j]
  if sum <= 0
    i = j+1
    if N[i] < 0
      shift i()
    sum = 0

Answer 1

我认为你的算法基本上是健全的，但它有两个bug我可以看到：

1. 在输入1-2103时，它将跳过10并输出3。我认为可以通过将I=++j；更改为I=j；.
来解决这个问题
2. 在两个不同的地方返回，如果j超过末尾，这将导致根本不产生输出！（例如，如果列表末尾出现一长串负数，就会发生这种情况。）

我也不希望它比卡丹的更快（或更慢，就此而言）。两个数的求和是一个快速的操作，就像将一个变量复制到另一个变量一样快，当您移动子数组的开始时，这就是您正在做的。