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)$ 。

全探索の方法では $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;
}