最大和子数组 O(n) 不是 Kadane 的

Maximum Sum Subarray O(n) not Kadane's

我正在读 Cormen 的 "Introduction to Algorithms"。

对于最大和子数组问题的线性算法,我提出了自己的解决方案。在实施之前没有检查现有的(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));
}

更新 代码的想法是只跟踪一个子数组,并添加到它的尾部数字,当数字太低以至于总和变为负数时 - 在尾部之后设置数组的开头。 此外,开头的负面项目将被忽略。子数组的头部只是向前移动。 每次总和似乎是最大值 - 更新 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

我认为你的算法基本上是正确的,但它有两个我能看到的错误:

  1. 在输入 1 -2 10 3 上,它将跳过 10 并输出 3。我认为您可以通过将 i = ++j; 更改为 i = j; 来解决此问题。
  2. 在 2 个不同的地方你 return 如果 j 超过了结尾,这将导致根本没有输出! (例如,如果列表末尾出现一长串负数,就会发生这种情况。)

我也不认为它会比 Kadane 的更快(或更慢)。将两个数字相加是一项快速的操作,就像将一个变量复制到另一个变量一样快,这就是您在移动子数组的开头时所做的。