C++ の最大部分配列問題

最大サブアレイ問題は、最大スライス問題と同じです。このチュートリアルでは、C++ でのコーディングの問題について説明します。問題は、配列内の連続した数字の可能なシーケンスの最大合計はいくつですか?これは配列全体を意味する場合があります。この問題とその解決策は、どの言語でも、最大部分配列問題と呼ばれます。配列には、負の数を含めることができます。

ソリューションは効率的でなければなりません。時間の複雑さを最速にする必要があります。現在のところ、ソリューションの最速のアルゴリズムは、科学界では Kadane のアルゴリズムとして知られています。この記事では、カダネのアルゴリズムを C++ で説明します。

データ例

次のベクトル (配列) を検討してください。

最大合計のスライス (部分配列) は、合計が 10 になるシーケンス {3, 5, -2, 4} です。他の可能なシーケンスは、配列全体であっても、最大で合計を与えることはできません。値は 10 です。配列全体の合計は 7 ですが、これは最大合計ではありません。

次のベクトルを検討してください。

最大合計のスライス (サブ配列) は、合計が 6 になるシーケンス {4, −1, 2, 1} です。最大合計のサブ配列内に負の数が存在する可能性があることに注意してください。

次のベクトルを検討してください。

合計が最大のスライス (部分配列) は、合計が 5 になるシーケンス {3, 2} です。

次のベクトルを検討してください。

最大合計の部分配列は、合計が 20 になるシーケンス {3, 2, 6, -1, 4, 5, -1, 2} です。これは配列全体です。

次のベクトルを検討してください。

ここには、合計が最大の 2 つのサブ配列があります。より高い合計は、最大サブアレイ問題の解 (答え) と見なされるものです。サブ配列は、合計が 12 の {5, 7} と、合計が 35 の {6, 5, 10, -5, 15, 4} です。もちろん、合計が 35 のスライスは答え。

次のベクトルを検討してください。

最大合計を持つ 2 つのサブ配列があります。より高い合計は、最大サブアレイ問題の解と見なされるものです。サブ配列は、合計が 34 の {10, 15, 9} と、合計が 26 の {4, 6, 3, 2, 8, 3} です。もちろん、合計が 34 のスライスは問題は、合計が最大のサブ配列ではなく、合計が最大のサブ配列を探すことであるため、答えです。

Kadane のアルゴリズムの開発

チュートリアルのこのセクションの情報は Kadane のオリジナルではありません。 Kadane のアルゴリズムを教えるための著者独自の方法です。上記のベクトルの 1 つと現在の合計を次の表に示します。

インデックスの累計は、インデックスの値を含む以前のすべての値の合計です。ここには合計が最大の 2 つのシーケンスがあります。それらは、合計が 12 になる {5, 7} と、合計が 35 になる {6, 5, 10, -5, 15, 4} です。合計が 35 になるシーケンスが必要です。 .

現在の合計には、値が 12 と 27 の 2 つのピークがあることに注意してください。これらのピークは、2 つのシーケンスの最後のインデックスに対応しています。

したがって、Kadane のアルゴリズムの考え方は、指定された配列内で左から右に移動しながら、遭遇した最大合計を比較しながら現在の合計を計算することです。

上記の別のベクトルと現在の合計を次の表に示します。

最大合計を持つ 2 つのシーケンスがあります。それらは {10, 15, 9} で、合計は 34 になります。 {4, 6, 3, 2, 8, 3} は、合計が 26 になります。合計が 34 になるシーケンスが必要です。

現在の合計には、値が 30 と 13 の 2 つのピークがあることに注意してください。これらのピークは、2 つのシーケンスの最後のインデックスに対応します。

繰り返しになりますが、Kadane のアルゴリズムの考え方は、指定された配列内で左から右に移動しながら、最大合計が検出されたときにそれらを比較しながら現在の合計を計算することです。

Kadane のアルゴリズムによる C++ でのコード

記事のこのセクションに記載されているコードは、Kadane が使用したものとは限りません。ただし、それは彼のアルゴリズムによるものです。このプログラムは、他の多くの C++ プログラムと同様に、次のように始まります。

名前空間 std を使用します。

入出力を担当する iostream ライブラリが含まれています。標準の名前空間が使用されます。

Kadane のアルゴリズムの考え方は、指定された配列内で左から右に移動しながら、最大合計を比較しながら現在の合計を取得することです。アルゴリズムの関数は次のとおりです。

指定された配列 (ベクトル) のサイズ N が決定されます。変数 maxSum は可能な最大合計の 1 つです。配列には、少なくとも 1 つの最大合計があります。変数 runTotal は、各インデックスの累計を表します。どちらも配列の最初の値で初期化されます。このアルゴリズムでは、配列内の次の値が現在の合計よりも大きい場合、その次の値が新しい現在の合計になります。

メインの for ループが 1 つあります。スキャンはゼロではなく 1 から始まります。これは、変数 maxSum と runTotal が指定された配列の最初の要素である A[0] に初期化されるためです。

for ループの最初のステートメントは、現在の値を以前のすべての値の累積合計に加算することによって、一時的な実行中の合計を決定します。

次に、if/else 構文があります。現在の値だけがこれまでの累計よりも大きい場合、その単一の値が累計になります。これは、指定された配列のすべての値が負の場合に特に便利です。この場合、最大の負の値だけが最大値 (答え) になります。現在の値だけがそれまでの一時的な現在の合計よりも大きくない場合、現在の合計は以前の現在の合計に現在の値を加えたものになります。これは if/else 構造の else 部分です。

for ループの最後のコード セグメントは、前のシーケンス（サブ配列）の以前の最大合計と現在のシーケンスの現在の最大合計のいずれかを選択します。したがって、より高い値が選択されます。複数の最大部分配列合計が存在する場合があります。配列が左から右にスキャンされるため、実行中の合計が増減することに注意してください。負の値を満たすと低下します。

最終的に選択されたサブ配列の最大合計は、for ループの後に返されます。

Kadane のアルゴリズム関数に適した C++ のメイン関数の内容は次のとおりです。

これにより、出力は次のようになります。

10

6

5

20

35

3.4

ここでの各行の回答は、指定された配列に順番に対応しています。

結論

Kadane のアルゴリズムの時間計算量は O(n) です。ここで、n は指定された配列の要素数です。この時間計算量は、最大サブアレイ問題で最速です。より遅いアルゴリズムは他にもあります。 Kadane のアルゴリズムの考え方は、指定された配列内で左から右に移動しながら、遭遇した最大合計を比較しながら現在の合計を計算することです。現在の値だけがこれまでの現在の合計よりも大きい場合、その単一の値が新しい現在の合計になります。それ以外の場合、指定された配列がスキャンされるため、予想どおり、新しい現在の合計は、以前の現在の合計に現在の要素を加えたものになります。

さまざまな可能なサブ配列に対して、複数の最大合計が存在する可能性があります。可能なすべてのサブアレイの最大合計が選択されます。

選択された最大合計の範囲の極限指数は? ――それはまたの機会に！

クリス