第11章

最大非セグメント和

（やさしい版） Pearls of Functional Algorithm Design（関数プログラミングによるアルゴリズム設計の真珠）

どんな問題？

整数のリスト（正の数も負の数も混ざっています）が与えられたとき、その部分列のなかで「連続していない部分列」だけを対象に、和が最大になるものを探すのがこの章のテーマです。

用語のおさらい

たとえば次のリストを考えます。

[−4, −3, −7, +2, +1, −2, −1, −4]
なぜ難しそうに見えるか 長さ n のリストのセグメントは Θ(n2) 個しかありませんが、部分列は Θ(2n) 個もあります。つまり非セグメントの数は指数的で、素朴に全部試すのは無理そうに見えます。それでも本章の目標は線形時間（O(n)）のアルゴリズムを導くことです。

仕様を書き下す

まずは「そのまま」書く

最大非セグメント和を mnss と呼びます。ずばり、次のように書けます。

mnss :: [Int] → Int mnss = maximum · map sum · nonsegs
Dart // 仕様どおりの素朴版: 全非セグメントを列挙し和を取り最大値を返す int mnssSpec(List<int> xs) { final segs = nonsegs(xs); return segs.map((ys) => ys.fold<int>(0, (a, b) => a + b)) .reduce((a, b) => a > b ? a : b); }

意味は「すべての非セグメントを列挙して、それぞれの和を計算し、その最大値を返す」というだけです。

非セグメントを「マーク付け」で表す

非セグメントを列挙するために、リストの各要素に True か False の印を付けます。True は「この要素を取る」、False は「取らない」という意味です。あらゆる印の付け方を試すのが markings です。

markings :: [a] → [[(a, Bool)]] markings xs = [zip xs bs | bs ← booleans (length xs)] booleans 0 = [[ ]] booleans (n+1) = [b : bs | b ← [True, False], bs ← booleans n]
Dart // 長さ n のブール列を全列挙 List<List<bool>> booleans(int n) { if (n == 0) return [<bool>[]]; final rest = booleans(n - 1); return [ for (final b in [true, false]) for (final bs in rest) [b, ...bs], ]; } // xs にブール印を付ける全パターン List<List<(T, bool)>> markings<T>(List<T> xs) { return booleans(xs.length) .map((bs) => [for (var i = 0; i < xs.length; i++) (xs[i], bs[i])]) .toList(); }

マーク付けと部分列は1対1に対応します。あとは「非セグメントに対応するマーク付け」だけをフィルタし、印の付いた要素を取り出せば nonsegs ができます。

nonsegs :: [a] → [[a]] nonsegs = extract · filter nonseg · markings extract :: [[(a, Bool)]] → [[a]] extract = map (map fst · filter snd)
Dart // 印が付いた要素だけ取り出す List<List<T>> extract<T>(List<List<(T, bool)>> mss) => mss.map((ms) => [for (final (x, b) in ms) if (b) x]).toList(); // 非セグメントだけを列挙 List<List<T>> nonsegs<T>(List<T> xs) => extract(markings(xs).where(nonseg).toList());

非セグメントを正規表現で見分ける

マーク付けが「非セグメント」であるかどうかは、真偽値の並びが次の正規表現にマッチするかどうかで判定できます（T=True、F=False と略記）。

F* T+ F+ T (T + F)*
読み方
  1. 先頭に F がいくつか（0 個でもよい）
  2. 次に T が 1 個以上
  3. 間に F が 1 個以上（=ギャップ）
  4. もう一度 T が現れる（これで「連続していない」ことが確定）
  5. あとは何が続いてもよい
つまり「一番左のギャップ」を見つけたら非セグメント、というルールです。

4 状態の有限オートマトンにする

この正規表現は、次の 4 つの状態を持つ有限オートマトンで認識できます。

data State = E | S | M | N
Dart // 4 状態のオートマトン enum State { E, S, M, N }

これを使うと nonseg は次のように書けます。

nonseg = (== N) · foldl step E · map snd
Dart // マーク付け全体が非セグメントか判定 bool nonseg<T>(List<(T, bool)> ms) => ms.map((p) => p.$2).fold(State.E, stepState) == State.N;

遷移関数 step の表は次のとおりです。

step E False = E step M False = M step E True = S step M True = N step S False = M step N False = N step S True = S step N True = N
Dart // オートマトンの遷移表 State stepState(State q, bool b) => switch ((q, b)) { (State.E, false) => State.E, (State.E, true) => State.S, (State.S, false) => State.M, (State.S, true) => State.S, (State.M, false) => State.M, (State.M, true) => State.N, (State.N, _) => State.N, };
大事な観察 ここで「非セグメント」であるかどうかに特別な事情はありません。有限オートマトンで判定できる性質なら、この章で紹介する同じ手順がそのまま使えます。

アルゴリズムの導出

作戦：foldl の融合則を使う

もう一度、目指す関数の定義を並べます。

mnss = maximum · map sum · extract · filter nonseg · markings extract = map (map fst · filter snd) nonseg = (== N) · foldl step E · map snd

作戦は次の 2 段構えです。

  1. extract · filter nonseg · markings の部分を「foldl の1回の折りたたみ」で書き直す。
  2. それに foldl の融合則を適用して、maximum · map sum と一体化した効率のよい foldl に変える。

状態ごとの「候補列」を持つ関数 pick

状態ごとに、その状態で終わるマーク付けから作れる部分列を集めた関数を pick と呼ぶことにします。

pick :: State → [a] → [[a]] pick q = extract · filter ((== q) · foldl step E · map snd) · markings
Dart // 状態 q で終わるマーク付けから作れる部分列を集める List<List<T>> pick<T>(State q, List<T> xs) { final ok = markings(xs).where( (ms) => ms.map((p) => p.$2).fold(State.E, stepState) == q).toList(); return extract(ok); }

とくに nonsegs = pick N です。pick は、次の 7 本の等式を満たします。

pick E xs = [[ ]] pick S [ ] = [ ] pick S (xs ++ [x]) = map (++[x]) (pick S xs ++ pick E xs) pick M [ ] = [ ] pick M (xs ++ [x]) = pick M xs ++ pick S xs pick N [ ] = [ ] pick N (xs ++ [x]) = pick N xs ++ map (++[x]) (pick N xs ++ pick M xs)
Dart // pick を末尾要素 x で 1 段展開する漸化式そのもの List<List<T>> pickRec<T>(State q, List<T> xs) { if (q == State.E) return [<T>[]]; if (xs.isEmpty) return <List<T>>[]; final init = xs.sublist(0, xs.length - 1); final x = xs.last; List<List<T>> app(List<List<T>> ys) => ys.map((l) => [...l, x]).toList(); return switch (q) { State.S => app([...pickRec(State.S, init), ...pickRec(State.E, init)]), State.M => [...pickRec(State.M, init), ...pickRec(State.S, init)], State.N => [ ...pickRec(State.N, init), ...app([...pickRec(State.N, init), ...pickRec(State.M, init)]), ], State.E => [<T>[]], }; }
読み方のコツ 各等式は「末尾に x を1つ追加したとき、それぞれの状態で作れる部分列がどう変化するか」を表しています。たとえば pick N (xs ++ [x]) は「x を取らない場合（pick N xs のまま）」と「x を取る場合（今まで N または M だったところに x を追加）」の合わせ技になっています。

4 つの状態をまとめて計算する pickall

4 状態ぶんの結果を 1 回のパスで求めるために、4 つ組を返す関数 pickall を導入します。

pickall xs = (pick E xs, pick S xs, pick M xs, pick N xs)
Dart // 4 状態の結果をまとめて返す typedef Quad<T> = (List<List<T>>, List<List<T>>, List<List<T>>, List<List<T>>); Quad<T> pickallSpec<T>(List<T> xs) => (pick(State.E, xs), pick(State.S, xs), pick(State.M, xs), pick(State.N, xs));

これは foldl として次のように書けます。

pickall = foldl step ([[ ]], [ ], [ ], [ ]) step (ess, nss, mss, sss) x = (ess, map (++[x]) (sss ++ ess), mss ++ sss, nss ++ map (++[x]) (nss ++ mss))
Dart // foldl 版: xs を左から一度だけなめて 4 状態を更新 Quad<T> pickall<T>(List<T> xs) { Quad<T> acc = ([<T>[]], <List<T>>[], <List<T>>[], <List<T>>[]); for (final x in xs) { final (ess, sss, mss, nss) = acc; List<List<T>> app(List<List<T>> ys) => ys.map((l) => [...l, x]).toList(); acc = ( ess, app([...sss, ...ess]), [...mss, ...sss], [...nss, ...app([...nss, ...mss])], ); } return acc; }

これで問題は次の形になります。

mnss = maximum · map sum · fourth · pickall
Dart // 4 番目の成分（pick N の結果）を取り、和の最大を返す int mnssViaPickall(List<int> xs) { final (_, _, _, nss) = pickall(xs); return nss.map((ys) => ys.fold<int>(0, (a, b) => a + b)) .reduce((a, b) => a > b ? a : b); }

ここで fourth は 4 つ組の 4 番目を取る関数です。

fourth を先頭に押し出す

4 つ組の各成分に同じ関数 f を適用する道具 tuple を用意します。

tuple f (w, x, y, z) = (f w, f x, f y, f z)
Dart // 4 つ組の全成分に同じ関数を適用 (B, B, B, B) tuple4<A, B>(B Function(A) f, (A, A, A, A) t) => (f(t.$1), f(t.$2), f(t.$3), f(t.$4));

すると次が成り立つので、

maximum · map sum · fourth = fourth · tuple (maximum · map sum)

mnss = fourth · tuple (maximum · map sum) · pickall と書き直せます。

融合則を適用する

foldl の融合則 任意の有限リスト xs について、
f a = b かつすべての x, y について f (g x y) = h (f x) y
が成り立つならば、
f (foldl g a xs) = foldl h b xs
が成り立つ、というルールです。

今回は次のように対応させます。

f = tuple (maximum · map sum) g = step a = ([[ ]], [ ], [ ], [ ])

あとは条件を満たす h と b を見つけるだけです。まず b は、

tuple (maximum · map sum) ([[ ]], [ ], [ ], [ ]) = (0, −∞, −∞, −∞)

となります（空集合の最大値は形式的に −∞ と約束しました）。

h の第4成分を計算する

4 成分それぞれについて条件式を解けば h が求まります。ここでは代表として第 4 成分を計算します（max = maximum の略）。

max (map sum (nss ++ map (++[x]) (nss ++ mss))) = {map の定義より} max (map sum nss ++ map (sum · (++[x])) (nss ++ mss)) = {sum · (++[x]) = (+x) · sum だから} max (map sum nss ++ map ((+x) · sum) (nss ++ mss)) = {max (xs ++ ys) = (max xs) max (max ys) だから} max (map sum nss) max (map ((+x) · sum) (nss ++ mss)) = {max · map (+x) = (+x) · max だから} max (map sum nss) max (max (map sum (nss ++ mss))) + x) = {n = max (map sum nss), m = max (map sum mss) を導入して} n max ((n max m) + x)

他の 3 成分も同じ要領で計算できて、最終的に次を得ます。

h (e, s, m, n) x = (e, (s max e) + x, m max s, n max ((n max m) + x))
Dart // 融合後の遷移: スコアの 4 つ組 (e, s, m, n) を x で更新 int _max(int a, int b) => a > b ? a : b; (int, int, int, int) h((int, int, int, int) t, int x) { final (e, s, m, n) = t; return (e, _max(s, e) + x, _max(m, s), _max(n, _max(n, m) + x)); }

そして次の一行が答えです。

mnss = fourth · foldl h (0, −∞, −∞, −∞)
Dart // 線形時間版: 4 つのスコアを 1 パスで更新するだけ int mnssFused(List<int> xs) { const negInf = -1 << 62; // 実質的な −∞ var acc = (0, negInf, negInf, negInf); for (final x in xs) { acc = h(acc, x); } return acc.$4; }
できたこと もはや部分列を列挙する必要はありません。リストを 1 回なめるだけで、各要素を処理するたびに 4 つのスコア (e, s, m, n) を更新していくだけで、最大非セグメント和が求まります。これは線形時間 O(n) のアルゴリズムです。

仕上げ：−∞ を消す

あとは仮想的な −∞ の扱いだけが残っています。もっとも簡単な対処は、最初の 3 要素を別扱いして、−∞ をそもそも使わないようにすることです。

mnss xs = fourth (foldl h (start (take 3 xs)) (drop 3 xs)) start [x, y, z] = (0, max [x+y+z, y+z, z], max [x, x+y, y], x+z)
Dart // 先頭 3 要素で初期状態を組み立て、−∞ を回避 (int, int, int, int) start(int x, int y, int z) => ( 0, [x + y + z, y + z, z].reduce(_max), [x, x + y, y].reduce(_max), x + z, ); int mnss(List<int> xs) { if (xs.length < 3) { // 3 要素未満ではそもそも非セグメントを作れない: 仕様外 throw ArgumentError('length must be >= 3'); } var acc = start(xs[0], xs[1], xs[2]); for (var i = 3; i < xs.length; i++) { acc = h(acc, xs[i]); } return acc.$4; }

見た目は少し野暮ったくなりますが、こちらのほうが実用的です。

Dart // 動作確認: [-4, -3, -7, 2, 1, -2, -1, -4] の最大非セグメント和 void main() { final xs = [-4, -3, -7, 2, 1, -2, -1, -4]; print(mnss(xs)); // 2 （例: [+2, +1, -1] を取ったとき） print(mnssFused(xs)); // 2 （−∞ を許した版でも同じ） print(mnssSpec(xs)); // 2 （素朴に全列挙した版でも同じ） }

終わりに

最大セグメント和問題そのものは 1975 年ごろに生まれ、Bentley (1987) のプログラミング真珠のひとつとして広まりました。不変表明による導出は Gries (1990) に、代数的な導出は Bird (1989) にあります。この問題はいまもデータマイニングやバイオインフォマティクスへの応用可能性から、変種が活発に研究されています（Mu (2008) など）。

この章の一番のメッセージ 非セグメント判定は「正規表現で書ける性質」の一例に過ぎません。同じ手順を使えば、次のような問題も同じ枠組みで解けます。

参考文献

Bentley, J. R. (1987). Programming Pearls. Reading, MA: Addison-Wesley.

Bird, R. S. (1989). Algebraic identities for program calculation. Computer Journal 32 (2), 122–6.

Gries, D. (1990). The maximum segment sum problem. In Formal Development of Programs and Proofs, ed. E. W. Dijkstra et al. University of Texas at Austin Year of Programming Series. Menlo Park. Addison-Wesley, pp. 43–5.

Mu, S.-C. (2008). The maximum segment sum is back. Partial Evaluation and Program Manipulation (PEPM '08), pp. 31–9.