0

目的: 以下の連続部分配列で最大和を見つけるためのアルゴリズムを評価します。

注：C++で書かれています

Kadane が動的計画法を使用してうまく解決した問題を調べていたとき、私はそれを解決する独自の方法を見つけるだろうと考えました。配列の両端を短くすることで合計を大きくできるかどうかに応じて、一連の再帰呼び出しを使用してこれを行いました。下記参照。

int corbins_largest_sum_continuous_subarray(int n, int* array){
   int sum = 0; // calculate the sum of the current array given
   for(int i=0; i<n; i++){sum += array[i];}

   if(sum-array[0]>sum && sum-array[n-1]>sum){
      return corbins_largest_sum_continuous_subarray(n-2, array+1);
   }else if(sum-array[0]<sum && sum-array[n-1]>sum){
      return corbins_largest_sum_continuous_subarray(n-1, array);
   }else if(sum-array[0]>sum && sum-array[n-1]<sum){
      return corbins_largest_sum_continuous_subarray(n-1, array+1);
   }else{ 
      return sum; // this is the largest subarray sum, can not increase any further
   }
}

Kadane のアルゴリズムが O(n) 時間かかることは理解しています。アルゴリズムの Big O の計算に問題があります。それもO(n)でしょうか？O(n) を使用して合計を計算するため、その後のすべての呼び出しは同じ時間を使用します。私のアルゴリズムは Kadane のアルゴリズムよりも有利ですか? Kadane のアルゴリズムはどのような点で優れていますか?

4

1 に答える 1

1

まず、式sum-array[0]>sumは と同等array[0]<0です。同様の観察が、コード内の他の条件にも当てはまります。

あなたのアルゴリズムは正しくありません。ここにあるコメントは真実ではありません:

}else{
    return sum // this is the largest subarray sum, can not increase any further
}

その時点に到達すると、外側の 2 つの値が両方とも正であることがわかりますが、配列内の別の場所に負の和のサブ配列が存在する可能性があり、これを削除すると、残りの 2 つのサブ配列が得られます。そのうちの 1 つ (またはboth) の合計が合計よりも大きくなる可能性があります。

たとえば、次の入力はそのような場合です。

[1, -4, 1]

アルゴリズムは、完全な配列 (合計は -2) を取得することによって最大の合計が達成されると結論付けますが、部分配列 [1] はより大きな合計を表します。

その他の反例:

[1, 2, -2, 1]
[1, -3, -3, 1, 1]
于 2020-02-01T09:09:58.920 に答える