読者です 読者をやめる 読者になる 読者になる

大学院生(情報科学)のブログ

モチベーション維持のためのブログです。

最大部分配列問題

要素の和を最大化する{A}の連続する部分配列を発見する問題を最大部分配列問題と呼ぶ.

例えば、配列{A[13,-3,-25,20,-3,-16,-23,18,20,-7,12,-5,-22,15,-4,7]}と与えられたとき、最大部分配列は{A[7 \cdots 10]}で和は43である.

この問題を分割統治を用いて解く.

分割は配列の中央点{mid}を基準にし{A[low \cdots mid]}{A[mid+1 \cdots high]}に分ける.この時、最大部分配列は{A[low \cdots mid]}{A[mid+1 \cdots high]}または、中央点をまたいで出現する.

また、部分配列は元の配列より小さいので、再帰的に最大部分配列を求める事ができる.

したがって、中央をまたぐ部分配列の中での最大部分配列を求め、求めた3つの部分配列の中から最大となるものを取り出せば良い.

{mid}は簡単に求まる.中央点をまたぐ最大部分配列は{A[i \cdots mid]}{A[mid+1 \cdots j]}を求め、結合すれば良い.

{find\_ max\_ crossing\_ array}は配列{A}と添字{low,mid,high}を引数とし、中央点をまたぐ最大部分配列の境界を定める2つの添字と最大部分列に属する要素の和を返す.

2,3行目で{A[i \cdots mid]}{A[mid+1 \cdots j]}の配列の初期化を行っている.
8行目の{for}文では{A[i \cdots mid]}の最大値を取る{i}を求める.10行目で{A[i+1 \cdots mid]}{A[i \cdots mid]}の大きさを比較し、{A[i \cdots mid]}の方が大きい場合、11行目で部分配列の先頭を{i}に更新する.

14行目の{for}文では同様にして、最大値を取る{A[mid+1 \cdots j]}を求める.

{find \_ max \_ crossing \_array}を用いて最大部分配列問題を解く{find\_ max\_ array}を以下に示す.

2行目の{if}文では要素が一つの配列、つまりインスタンスが基底か否かを判定する.基底の場合、要素はただ一つであるので、この要素の添字を両端の添字とし、その添字と要素を3行目で返している.
5行目では中間点を計算する.6行目で左最大部分配列、7行目では右最大部分配列を再帰的に決定する.8行目は中央点をまたぐ最大部分配列を求めている.
9行目からの条件分岐で3つの部分配列を比較し、最大となる配列を最大部分配列とし結果を返している.

実行結果
{A = [13,-3,-25,20,-3,-16,-23,18,20,-7,12,-5,-22,15,-4,7] \\
print\;find\_ max\_ array(A,0,len(A)-1)\\
(7,10,43)}