部分列の和の最大化

珠玉のプログラミング コラム8より。

a[x], x=0, 1, .., N-1という配列の部分列の和の最大値を考える。ここで、

• 部分列は、あるs,t：0≦s ≦t≦N-1を用いて、a[s], a[s+1], .., a[t]で与えられるものを考える
• a[x]は、任意の実数

上のような最大値を配列の最大部分列和と呼ぶ。

愚直解：

部分列の個数は、O(N^2)。それぞれの和の計算にO(N)時間。よって、愚直に実行するとO(N^3)

O(N^2)：

cumsumを作っておけば（O(N)で構築可能）、任意の部分列の和はO(1)で計算可能。よって、O(N^2)で最大化可能

O(N logN)：

簡単な分割統治を考える。

1. 配列を0..mとm+1..N-1に2つに分割
2. 求めたい答えは、
   • a) 0..mの部分列の和の最大 or
   • b) m+1..N-1の部分列の最大 or
   • c) s..m, m+1..t の形の列の和の最大

のいずれか

2において、cの計算は、O(N)で実行可能。再帰の深さはO(logN)になるので、全体としてO(N logN)で実行可能。

2-cの計算は、s,tをバラバラに動かせることで、O(N)が達成される。

max(a[s] + .. + a[m] + a[m+1] + .. + a[t]) = max(a[s] + .. + a[m]) + max(a[m+1] + .. + a[t])

よく考えると、O(N logN)という評価は、少しまじめに考えないとだめ。2-cの計算が、O(N)で実行可能なことは間違いないが、この評価では上限が緩すぎる。再帰の「深さ」は確かにO(logN)だが、再帰関数の呼び出し回数自体はO(N)回ある：長さNに対して1回、長さN/2に対して2回、長さN/4に対して4回・・・なので、1+2+..+2^(logN)回くらいの呼び出しがある。したがって、2-cの計算がO(N)であるという評価だけでは、アルゴリズム全体の評価はO(N^2)時間となってしまう。 ポイントは、深さが深くなるに従って、呼び出し回数は増えるが同時に部分列の長さは小さくなっていくことである。各深さにおける列の長さの合計（≒必要な足し算と比較の回数）がO(N)となっていることが必要であった。

厳密な議論をするには、長さnの問題を解く時間をT(n)としたときに

T(n) = 2T(n/2) + O(n)

という漸化式が成り立つことから、T(n)の評価を行う。

O(N)：

a[0..t]に対して、任意の部分列ではなく、終点がtであるような部分列 or 空列の中での最大和をM1[t]と置く。 この時、

M1[t] = max(M1[t-1] + a[t], 0)

が成り立つ。この漸化式を使うと、M1[t]はO(N)で求まる。 最大部分列和は、M1[t]の最大値なので、O(N)で求まる。結局、全体でもO(N)しかかからない。