0

I'm reading Cormen's "Introduction to Algorithms".

For the linear algorithm for Max Sum Subarray problem I came up with my own solution. Didn't check existing one (Kadena's) before implementing.

Now I'm testing it with different test scenarios and always have better results than Kadena's. I don't believe in such a luck, but can't find what have I missed. Could you take a look whether it is a working solution?

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

Update The idea of code is to keep in track only one subarray, and adding to its' tail numbers, when numbers are that low that sum becomes negative - set beginning of array after the tail. Additionally negative items in the beginning are being ignored. head of subarray is just shifted forward. Everytime sum appears to be maximum - maxSum and limits are updated.

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
4

1 回答 1

0

我认为您的算法基本上是合理的，但我可以看到它有两个错误：

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

此外，我不认为它会比 Kadane 的更快（或更慢）。将两个数字相加是一种快速操作，就像将一个变量复制到另一个变量一样快，这就是您在移动子数组的开头时所做的事情。

于 2015-03-22T19:41:16.767 回答