Ark's Blog

参加記や備忘録などを書いていきます

ようこそ

Kadane’s Algorithm | 最大部分配列 問題

DPについて調べてたらKadane's algorithmという聞いたことないアルゴリズムが出てきたので調べてみた。

Kadane's algorithmは、最大部分配列問題(maximum subarray problem)をO(n)で解くアルゴリズムみたいです。 以下は、最大部分配列問題とそれを解くアルゴリズムの解説です。

最大部分配列問題とは

最大部分配列問題(maximum subarray problem)とは、与えられた配列に対して、その(連続した)部分配列のうち和が最大となるものの値を求める問題のことです。

形式化すると次のようになります。(添字は0-basedとします)

  • 入力: 大きさ nの数列\displaystyle  \{a_i\}_{i=0}^{n-1}
  • 出力:  \displaystyle\max \left\{ \sum_{k=i}^j a_k \mathrel{\bigg|} 0\leq i \leq j \lt n \right\}

以下、

 \displaystyle x:= \max \left\{ \sum_{k=i}^j a_k \mathrel{\bigg|} 0\leq i \leq j \lt n \right\}

とおきます。

解法

  • 全探索1: O(n^3)
  • 全探索2: O(n^2)
  • Divide and Conquer:  O(n\log n)
  • Kadane's algorithm:  O(n)

全探索1

普通に全探索します。

long solve(int n, long[] as) {
    long res = -INF;
    foreach(i; 0..n) {
        foreach(j; i..n) {
            long s = 0;
            foreach(k; i..j+1) {
                s += as[k];
            }
            res = max(res, s);
        }
    }
    return res;
}

コードはD言語ですが、何やってるかはノリでわかると思います。計算量はO(n^3)

数式で表すと、

\begin{align} x &= \max_{0\leq i < n} \left\{ \max_{i \leq j < n} \left\{ \sum_{k=i}^j a_k \right\} \right\}\\ \end{align}

気持ちこんな感じです。

全探索2

全探索1では \displaystyle \sum_{k=i}^j a_kを各i,jで求めてますが、累積和を逐次計算すれば計算量を落とせます。

long solve(int n, long[] as) {
    long res = -INF;
    foreach(i; 0..n) {
        long s = 0;
        foreach(j; i..n) {
            s += as[j];
            res = max(res, s);
        }
    }
    return res;
}

計算量はO(n^2)

Divide and Conquer

分割統治法です。詳しくは書きませんが、マージソートの要領で計算します。
区間を半分に分けてさらにその区間を半分に分けて・・・って分割した後にそれらの計算結果を分割とは逆順に徐々にマージしていきます。

計算量はO(n\log n)

Kadane's algorithm

全探索の方法では x

\begin{align} x &= \max_{0\leq i < n} \left\{ \max_{i \leq j < n} \left\{ \sum_{k=i}^j a_k \right\} \right\}\\ \end{align}

と変形していましたが、 i j\maxを交換して次のように変形することを考えます。

\begin{align} x &= \max_{0\leq j < n} \left\{ \max_{0 \leq i \leq j} \left\{ \sum_{k=i}^j a_k \right\} \right\}\\ \end{align}

ここで \displaystyle s_j := \max_{0 \leq i \leq j} \left\{  \sum_{k=i}^j a_k \right\} とおくと、 \displaystyle x = \max_{0\leq j \lt n} \{s_j\}となります。また、 s_0 = a_0です。

さらに ^\forall j \gt 0に対して次の関係式が成り立ちます。

\begin{align} s_{j} &= \max_{0 \leq i \leq j} \left\{ \sum_{k=i}^j a_k \right\} \\ &= \max\left\{ \max_{0 \leq i \leq j-1} \left\{ \sum_{k=i}^j a_k \right\}, \max_{j \leq i \leq j} \left\{ \sum_{k=i}^j a_k \right\} \right\} \\ &= \max\left\{ \max_{0 \leq i \leq j-1} \left\{ \sum_{k=i}^{j-1} a_k \right\} + a_j, a_j \right\} \\ &= \max\{ s_{j-1} + a_j, a_j\} \end{align}

つまり

  •  s_0 = a_0
  •  ^\forall j \gt 0に対して s_{j} = \max\{ s_{j-1} + a_j, a_j\}

より、すべての s_jを計算するのに O(n)で済みます。

あとはこれらs_j \maxを取ることで xが得られるので、全体の計算量は O(n)です。

コードにすると次のようになります。

long solve(int n, long[] as) {
    long res = -INF;
    long s = 0;
    foreach(j; 0..n) {
        s = max(s + as[j], as[j]);
        res = max(res, s);
    }
    return res;
}

テスト

ちょうどAOJにMaximum Sum Sequence用の問題があったのでテストに使いました。

参考