java - 最大合計部分配列 O(n) は Kadane のものではありません

Question

Cormen の「Introduction to Algorithms」を読んでいます。

Max Sum Subarray 問題の線形アルゴリズムについては、独自の解決策を考え出しました。実装前に既存のもの（カデナのもの）をチェックしていませんでした。

現在、さまざまなテスト シナリオでテストしており、常に 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));
}

更新 コードの考え方は、1 つのサブ配列のみを追跡し、その末尾の数値に追加することです。数値が非常に低い場合、合計が負になるため、末尾の後に配列の先頭を設定します。さらに、冒頭の否定的な項目は無視されています。サブ配列の先頭が前方にシフトされます。合計が最大に見えるたびに - 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