最大部分配列和 (Kadane)

全部の区間を試すと間に合わない

[-2, 1, -3, 4, -1, 2, 1, -5, 4] から連続した区間を 1 つ選んで、合計を一番大きくします。答えは 4, -1, 2, 1 の 6 です。今度は飛ばせません。区間なので、始まりと終わりを決めたら、間の要素は全部入ります。

始まりと終わりを総当たりすると、こんな形になります。

正しい答えは出ますが、要素が 10 万個になると 50 億回の足し算になります。配列を 1 度通り抜けるだけで答えを出したいところです。

足を引っ張るなら、そこで捨てる

左から 1 個ずつ見ていき、「今の要素で終わる区間の合計」だけを持ち歩きます。次の要素が来たときの判断は 1 つだけです。

これまでの合計がマイナスなら、そこまでを捨てて、新しい要素から始め直す。

理由は単純です。これまでの合計がマイナスなら、それを引き継いだ時点で、次の要素の単独より必ず小さくなります。プラスなら、引き継いだほうが必ず大きくなります。次の要素が何であるかは関係ありません。だから、その場で決めてしまってよいのです。

先ほどの配列で追ってみます。

• -2 から始めて合計は -2。マイナスなので捨てる
• 1 から始め直して合計 1
• 次は -3。1 はプラスなので引き継いで合計 -2。マイナスになった
• 次は 4。捨てて 4 から始め直す
• -1 を足して 3、2 を足して 5、1 を足して 6
• 次は -5。6 はプラスなので引き継いで 1
• 最後の 4 を足して 5

途中で出てきた一番大きい値は 6 です。捨てるか引き継ぐかを、その場の合計だけで決められるのがこの解き方の肝です。先の要素を見に行く必要がないので、配列を左から 1 度なぞるだけで答えが出ます。

ですから持ち歩くのは「今の合計」と「今までで一番大きかった値」の 2 つだけで足ります。今の合計が下がったときに一番大きかった値まで下げてしまわないよう、2 つは別々に持ちます。

全部マイナスのときに 0 を返さない

よくある書き間違いは、合計がマイナスになったときに 0 に戻してしまうことです。それだと [-3, -1, -2] でも 0 を返しますが、この課題は 1 要素以上を必ず選ぶ ので、答えは -1 です。

0 に戻すのではなく、その要素の値から始め直す。こう書いておけば、全部マイナスでも自然に一番大きい単独の要素が残ります。一番大きかった値を入れる変数も、0 ではなく先頭の要素で始めます。

やってみよう

• [5, 4, -1, 7, 8] は全部足すのが最大で 23。途中の -1 を捨てないほうが得
• [-1] の答えは -1。要素が 1 つならそれを選ぶしかない
• [42] のように 1 要素だけの配列で、ループが 1 度も回らなくても答えが出るか確かめる
• どこからどこまでを選んだかも返したい場合を考える。捨てて始め直した位置が、区間の始まりになる

1. 戻り値は連続部分配列の最大和 (整数)
2. 1 要素以上を必ず選ぶ (空区間は不可、全要素負のときは最大の単独要素を返す)
3. Kadane のアルゴリズム O(n) で解くこと