Максимальная сумма Subarray O(n) не Kadane's

Question

Я читаю "Введение в алгоритмы" Кормена.

Для линейного алгоритма для задачи Max Sum Subarray я придумал собственное решение. Не проверял существующий (Кадена) перед внедрением.

Сейчас я тестирую его с разными сценариями тестирования и всегда получаю лучшие результаты, чем у Кадены. Я не верю в такую ​​удачу, но не могу найти то, что я пропустил. Не могли бы вы посмотреть, является ли это рабочим решением?

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

Answer 1

Я думаю, что ваш алгоритм в основном здоров, но в нем есть две ошибки, которые я вижу:

1. На входе 1 -2 10 3, он пропустит 10 и выводит 3. Я думаю, вы можете исправить это, изменив i = ++j; в i = j;,
2. В 2 разных местах вы return если j проходит через конец, что не приведет ни к какому результату! (Это произойдет, если, например, длинный список отрицательных чисел появится в конце списка.)

Также я не ожидаю, что это будет быстрее (или медленнее, в этом отношении), чем у Кадане. Суммирование двух чисел - это быстрая операция, такая же, как копирование одной переменной в другую, что вы и делаете, когда сдвигаете начало подмассива.