最大部分配列問題

コンピュータサイエンスにおいて、最大和部分配列問題（最大セグメント和問題とも呼ばれる）は、与えられた1次元の数値配列A[1...n]内で、合計が最大となる連続部分配列を見つける問題である。これは、時間と空間の制約内で解くことができる。 ${\displaystyle O(n)}$${\displaystyle O(1)}$

正式には、このタスクは、と のインデックスを見つけ、その合計が ${\displaystyle i}$${\displaystyle j}$${\displaystyle 1\leq i\leq j\leq n}$

${\displaystyle \sum _{x=i}^{j}A[x]}$

は可能な限り大きくなります。（問題のいくつかの定式化では、空の部分配列も考慮されます。慣例により、空の部分配列のすべての値の合計はゼロになります。）入力配列Aの各数値は、正、負、またはゼロのいずれかになります。^[1]

たとえば、値の配列 [−2, 1, −3, 4, −1, 2, 1, −5, 4] の場合、合計が最大となる連続サブ配列は [4, −1, 2, 1] で、合計は 6 になります。

この問題のいくつかの特性は次のとおりです。

1. 配列にすべて非負の数値が含まれている場合、問題は簡単です。最大のサブ配列は配列全体です。
2. 配列に正でない数値がすべて含まれている場合、解は配列の最大値 (または許可されている場合は空の部分配列) を含むサイズ 1 の任意の部分配列になります。
3. 複数の異なるサブ配列の最大合計が同じになる場合があります。

この問題は、ブルートフォース法、^[2]分割統治法、^[3]動的計画法、^[4]最短経路への縮小法など、いくつかの異なるアルゴリズム手法を使用して解決できますが、Kadaneアルゴリズムと呼ばれる単純なシングルパスアルゴリズムによって効率的に解決されます。

最大サブアレイ問題は、デジタル画像内のパターンの最大尤度推定のための簡略化されたモデルとして、1977年にウルフ・グレナンダーによって提案されました。 ^[5]

Grenander は、実数の 2 次元配列で、合計が最大となる長方形の部分配列を探していました。2 次元の問題に対するブルート フォース アルゴリズムは O(n6) 時間で実行されます^。このアルゴリズムでは実行時間が長すぎるため、Grenander は 1 次元の問題の構造を理解するために 1 次元^の問題を提案しました。Grenander は、1 次元の問題をO ( n2 ) 時間で解くアルゴリズムを導き出し、^{[注 1]} ブルート フォースの実行時間O ( n3 )を改善しました。この問題について聞いたMichael Shamos は、一晩でO ( ^nlogn )の分割統治アルゴリズムを考案しました。その後すぐに、Shamos は、1 次元の問題とその歴史について、Jay Kadaneも出席したカーネギーメロン大学のセミナーで説明しました。Kadane は、1 分以内に可能な限り高速なO ( n ) 時間のアルゴリズム^{[5] [6] [7]を設計しました。 [注2]} 1982年にデイビッド・グリースはダイクストラの「標準戦略」を適用して同じO ( n )時間アルゴリズムを導き出しました。 ^[8] 1989年にリチャード・バードはバード・メルテンス形式を用いたブルートフォースアルゴリズムの純粋に代数的な操作によってそれを導き出しました。^[9]

グレナンダーの2次元一般化は、カダネのアルゴリズムをサブルーチンとして使用するか、分割統治法によってO(n3)時間で解くことができる^。距離行列の乗算に基づくわずかに高速なアルゴリズムは、Tamaki & Tokuyama (1998)およびTakaoka (2002)によって提案されている。大幅に高速なアルゴリズムは存在しないという証拠がある。任意のε>0に対して2次元最大サブアレイ問題をO( n3 ^{−ε )時間で解くアルゴリズムは、}全ペア最短経路問題に対して同様に高速なアルゴリズムを意味する。^[10]

最大サブアレイ問題は、ゲノム配列解析やコンピュータービジョンなど、多くの分野で発生します。

ゲノム配列解析では、認識すべきモチーフが存在する場合は陽性、存在しない場合は陰性の配列内の点にスコアを割り当て、これらのスコアの中で最大のサブアレイを探すことにより、異常な特性を持つタンパク質配列の重要な生物学的セグメントを識別するために最大サブアレイアルゴリズムを採用しています。これらの問題には、保存されたセグメント、GCに富む領域、タンデムリピート、低複雑性フィルター、DNA結合ドメイン、高電荷領域が含まれます。^[11]

コンピュータビジョンでは、ビットマップ画像は通常、正の値のみで構成されているため、最大サブ配列問題は簡単です。結果は常に配列全体になります。ただし、各ピクセルからしきい値（平均ピクセル値など）を減算して、平均以上のピクセルが正になり、平均以下のピクセルが負になるようにした後、最大サブ配列問題を変更された画像に適用して、画像内の明るい領域を検出できます。^[12]

Kadane のアルゴリズムは、指定された配列を左から右にスキャンします。番目のステップでは、 で終わる合計が最大になるサブ配列を計算します。この合計は変数 に保持されます。^{[注 3]} さらに、 内の任意の場所にある合計が最大になるサブ配列を計算し、変数に保持します。^{[注 4]}これは、これまでに見た のすべての値の最大値として簡単に取得できます(アルゴリズムの 7 行目を参照)。 ${\displaystyle A[1\ldots n]}$${\displaystyle j}$${\displaystyle j}$current_sum${\displaystyle A[1\ldots j]}$best_sumcurrent_sum

ループ不変条件として、番目のステップでは、 の古い値が合計全体にわたって最大値を保持します。したがって、^{[注 5] は}合計 全体にわたって最大値です。後者の最大値が の場合もカバーするように拡張するには、シングルトン サブ配列 も考慮すれば十分です。これは、6 行目で の新しい値として を割り当てることによって行われ、その後、この値は合計全体にわたって最大値を保持します。 ${\displaystyle j}$current_sum${\displaystyle i\in \{1,\ldots ,j-1\}}$${\displaystyle A[i]+\cdots +A[j-1]}$current_sum${\displaystyle +A[j]}$${\displaystyle i\in \{1,\ldots ,j-1\}}$${\displaystyle A[i]+\cdots +A[j]}$${\displaystyle i=j}$${\displaystyle A[j\;\ldots \;j]}$${\displaystyle \max(A[j],}$current_sum${\displaystyle +A[j])}$current_sum${\displaystyle i\in \{1,\ldots ,j\}}$${\displaystyle A[i]+\cdots +A[j]}$

したがって、この問題はPythonで表現された次のコード^[13]で解決できます。

def  max_subarray (数値):
    「連続する部分配列の最大の合計を求めます。」
    best_sum  =  float ( '-inf' )
    現在の合計 =  0
     数値のx について: 
        現在の合計 = 最大( x 、 現在の合計 +  x )
        ベスト合計 = 最大(ベスト合計、 現在合計)
     best_sumを返す

入力に正の要素が含まれていない場合、返される値は最大要素の値 (つまり、0 に最も近い値) になります。入力が空の場合は、負の無限大になります。正確性を保つために、入力配列が空の場合は例外を発生させる必要があります。空の配列には最大の空でないサブ配列がないためです。配列が空でない場合、数値と非数値の混在を避けるために、必要に応じて、負の無限大の代わりに配列の最初の要素を使用できます。

このアルゴリズムは、空のサブ配列を許可する場合や、最大サブ配列の開始インデックスと終了インデックスを追跡する場合に適応できます。

このアルゴリズムは、前の位置で終わる最大サブ配列から各位置で終わる最大サブ配列を計算するため、動的計画法の単純なケースとして見ることができます。

Kadaneのオリジナルアルゴリズムは、空の部分配列が許容される場合に問題の変種を解く。^{[4] [7]} この変種は、入力に正の要素が含まれていない場合（入力が空の場合を含む）は0を返す。これは、コードの2つの変更によって得られる。3行目では、best_sum空の部分配列を考慮して0に初期化する必要がある。${\displaystyle A[0\ldots -1]}$

    ベスト合計 =  0 ;

forループの6行目はcurrent_sum次のように更新されるmax(0, current_sum + x)。^{[注 6]}

        現在の合計 = 最大( 0 , 現在の合計 +  x )

ループ不変条件として、番目のステップでは、 の古い値が合計全体にわたって最大値を保持します。^{[注 7]} したがって、 は合計 全体にわたって最大値です。後者の最大値が の場合もカバーするように拡張するには、空の部分配列 も考慮するだけで十分です。これは、6 行目で の新しい値として を割り当てることによって行われ、その後、この値は合計全体にわたって最大値を保持します。両方のバリアントの機械検証済みC / Frama-Cコードは、こちらで入手できます。 ${\displaystyle j}$current_sum${\displaystyle i\in \{1,\ldots ,j\}}$${\displaystyle A[i]+\cdots +A[j-1]}$current_sum${\displaystyle +A[j]}$${\displaystyle i\in \{1,\ldots ,j\}}$${\displaystyle A[i]+\cdots +A[j]}$${\displaystyle i=j+1}$${\displaystyle A[j+1\;\ldots \;j]}$${\displaystyle \max(0,}$current_sum${\displaystyle +A[j])}$current_sum${\displaystyle i\in \{1,\ldots ,j+1\}}$${\displaystyle A[i]+\cdots +A[j]}$

アルゴリズムを変更して、最大サブ配列の開始インデックスと終了インデックスも追跡できます。

このアルゴリズムは最適なサブ構造を使用する方法 (各位置で終了する最大サブ配列は、関連しているがより小さく重複するサブ問題 (前の位置で終了する最大サブ配列) から簡単な方法で計算されます) のため、このアルゴリズムは動的プログラミングの単純で自明な例として見ることができます。

Kadaneのアルゴリズムの実行時複雑度はであり、空間複雑度はである。^{[4] [7]}${\displaystyle O(n)}$${\displaystyle O(1)}$

同様の問題が高次元配列に対しても提起される可能性がありますが、その解決方法はより複雑です。たとえば、Takaoka (2002) を参照してください。Brodal と Jørgensen (2007) は、最適な時間制限内で、1 次元配列内のk個の最大サブ配列の合計を見つける方法を示しました。 ${\displaystyle O(n+k)}$

k個の分離したサブ配列の最大和も最適な時間境界内で計算することができる 。^[14]${\displaystyle O(n+k)}$

• 部分集合の和の問題

• Alves, Carlos ER; Cáceres, Edson; Song, Siang W. (2004)、「最大サブシーケンスと最大サブアレイの BSP/CGM アルゴリズム」、Kranzlmüller, Dieter; Kacsuk, Péter; Dongarra, Jack J. (編)、並列仮想マシンとメッセージ パッシング インターフェイスの最近の進歩、第 11 回ヨーロッパ PVM/MPI ユーザー グループ ミーティング、ハンガリー、ブダペスト、2004 年 9 月 19 ～ 22 日、議事録、Lecture Notes in Computer Science、vol. 3241、Springer、pp. 139 ～ 146、doi :10.1007/978-3-540-30218-6_24、ISBN 978-3-540-23163-9
• Backurs, Arturs; Dikkala, Nishanth; Tzamos, Christos (2016)、「最大重量長方形の厳密な硬さの結果」、Proc. 43rd International Colloquium on Automata, Languages, and Programming : 81:1–81:13、doi : 10.4230/LIPIcs.ICALP.2016.81、S2CID  12720136
• Bae, Sung Eun (2007)、一般化最大サブアレイ問題に対する逐次的および並列アルゴリズム(PDF) (博士論文)、カンタベリー大学、S2CID 2681670、2017-10-26に オリジナル(PDF)からアーカイブ。
• Bae, Sung Eun; Takaoka, Tadao (2006)、「\emph{K}-最大サブアレイ問題に対する改良アルゴリズム」、The Computer Journal、49 (3): 358–374、doi :10.1093/COMJNL/BXL007
• Bengtsson, Fredrik; Chen, Jingsen (2007)、最大スコアセグメントの最適な計算(PDF) (研究レポート)、ルレオ工科大学
• ベントレー、ジョン(1984)、「プログラミングの秘訣: アルゴリズム設計テクニック」、Communications of the ACM、27 (9): 865–873、doi :10.1145/358234.381162、S2CID  207565329
• ベントレー、ジョン（1989年5月）、プログラミングパール（第2版）、マサチューセッツ州レディング：アディソンウェスリー、ISBN 0-201-10331-1
• バード、リチャード S. (1989)、「プログラム計算のための代数的恒等式」、コンピュータジャーナル、32 (2): 122–126、doi :10.1093/comjnl/32.2.122
• ブローダル、ガース・ストルティング。 Jørgensen、Allan Grønlund (2007)、「 k最大和問題の線形時間アルゴリズム」、 Mathematical Foundations of Computer Science 2007、Lecture Notes in Computer Science、vol. 4708、Springer-Verlag、pp. 442–453、doi :10.1007/978-3-540-74456-6_40、ISBN 978-3-540-74455-9。
• Gries, David (1982)、「ループ不変条件とループを開発するための標準戦略に関する注記」(PDF)、コンピュータプログラミングの科学、2 (3): 207–241、doi :10.1016/0167-6423(83)90015-1、hdl :1813/6370
• Ruzzo, Walter L.; Tompa, Martin (1999)、「すべての最大スコアリング サブシーケンスを見つけるための線形時間アルゴリズム」、Lengauer, Thomas; Schneider, Reinhard; Bork, Peer; Brutlag, Douglas L.; Glasgow, Janice I.; Mewes, Hans-Werner; Zimmer, Ralf (編)、Proceedings of the Seventh International Conference on Intelligent Systems for Molecular Biology、1999 年 8 月 6 ～ 10 日、ハイデルベルク、ドイツ、AAAI、pp. 234 ～ 241
• 高岡忠雄 (2002)、「距離行列乗算による最大サブアレイ問題の効率的なアルゴリズム」、電子計算機科学理論ノート、61 : 191–200、doi : 10.1016/S1571-0661(04)00313-5。
• 玉置久雄、徳山武 (1998)、「行列乗算に基づく最大部分配列問題の解法」、第 9 回離散アルゴリズムシンポジウム (SODA) 論文集: 446–452、ISBN 978-0-89871-410-4、 2018年11月17日閲覧
• ウェッデル、スティーブン・ジョン、リード、トリスタン、タハー、モハメッド、高岡、忠雄 (2013)、「天文画像撮影における最大サブアレイアルゴリズム」、Journal of Electronic Imaging、22 (4): 043011、Bibcode :2013JEI....22d3011W、doi :10.1117/1.JEI.22.4.043011

• TAN, Lirong. 「最大連続サブ配列和問題」(PDF)。2015-10-10 にオリジナル(PDF)からアーカイブ。2017-10-26に取得。
• Mu, Shin-Cheng (2010)。「最大セグメント和問題：その起源と導出」。
• 「最大サブアレイ問題に関するノート」 2012年。
• 翻訳:
• アレクセイゴル
• Rosetta Code における最大連続和問題
• geeksforgeeks の Kadane のアルゴリズムのページ