📝

Kadane's Algorithm -部分和の最大値を求める-

に公開
C++
競技プログラミング
AtCoder
アルゴリズム
LeetCode
tech

はじめに

本記事では配列の連続する部分列のうちその総和の最大値を求めるアルゴリズムであるKadane's Algorithmを解説します。使用する言語はC++です。

問題設定

以下のような問題を解決する.

長さNの整数列A=\{A_0, A_1,...,A_{N-1}\}が与えられる.
この時連続する部分列でその総和が最大となる時その値を求めよ.

つまり

長さNの整数列A=\{A_0, A_1,...,A_{N-1}\}, 0≤l≤r<Nを満たす整数l, rについて,

\sum_{i=l}^{r}A_i

の最大値を求めよ.

という問題である.
以下では部分列の総和を部分和という.
ここでAの全ての要素が非負の時はもちろん A全体を部分列として選択することでそれが解となるのでこれ以降はさらに制約として

  • 入力は全て整数
  • 1\le N\le 3×10^5
  • \textcolor{red}{-10^6}\le A_i\le 10^6

を追加する.

イメージできない人のための具体例
A = \{-3, -1, 3, 8, 0, 2, -6, 8, -7, -1\}

の時, l=2, r=7の部分列

\{3, 8, 0, 2, -6, 8\}

を選択すると, その総和は3+8+0+2+(-6)+8=15で最大となる.

これを時間計算量O(N)で計算していこうというのがKadane's Algorithmである.

力ずく探索

一番力ずくな解法として全てのl, rの組に対して総和を求める全探索の解法があるがこれは時間計算量がO(N^2)となるので本制約下では実行時間制限に間に合わない.

力ずく探索の計算量解析

l,rの組の数が{}_n \mathrm{C}_2=\frac {n(n-1)}{2}つまりO(N^2)個ある.それぞれの累積和を前もって計算しておくことでそれぞれのl, rの組に対してO(1)の計算で部分和を求めることができる.
つまりこの計算量はO(N^2)となる.

Kadane's Algorithm

そこでKadane's Algorithmの登場である.
このアルゴリズムのメインのロジックはDP(動的計画法)である.
一次元の大きさNの以下のような定義の配列\mathrm{DP}を用意する.

\mathrm{DP}[i]: \text{A[i]で終わる部分列のうち総和が最大となる時の総和}

遷移を考えていく. 次の時点(\mathrm{A[i]}に着目している時)での最大値の候補は

\mathrm{DP}[i] = \begin{cases} \mathrm{DP}[i-1] + A[i] \\ A[i] \end{cases}

のどちらかである. これらのどちらが選択されるかというと,

  1. \mathrm{DP[i]=DP[i-1]+A[i]}
    現時点で最大値の候補としている部分列(\mathrm{A[i-1]}まで続いているもの)の最後尾に\mathrm{A[i]}を付け足した部分列
  2. \mathrm{DP[i]=A[i]}
    ここまでの部分列の最大値が負の時に\mathrm{A[i]}単体を部分列と取る.
    ここから1. を伸ばしていくイメージ.

上の図において水色の続いてきている部分列(a[i-2], a[i-1], a[i])を最大値として保管する.
それより緑単体の方が大きければa[i]を新しい部分列(の先頭)として採用する.

あとは, DP[i]つまり
” \mathrm{A[i]}で終わる部分列の中で総和が最大のもの”
の中から最大値を探せば良い.
\mathrm{A[0]}, \mathrm{A[1]},...\mathrm{A[N-1]}のどこかに最大値を与える部分列の終点があるからである.

DPの初期化は問題に依って異なり, 求める部分列について,

  1. 長さ0(\mathrm{l=r})が許容されている
    この時は長さ0の部分列も解の候補であるから,
    \mathrm{DP[i]=0}
  2. 長さ1以上(\mathrm{l<r})
    この時は
    \mathrm{DP[i]=A[0]}

    で最大値を初期化する.

実装

int main(){
    vector<int> A = {-3, -1, 3, 8, 0, 2, -6, 8, -7, -1};
    int N　=　A.size();
    vector<int> DP(N);
    DP[0] = A[0];
    for(int i = 1; i < N; i++){
        DP[i] = max(DP[i-1] + A[i], A[i]);
    }
    int ans=0;
    for(int i = 0; i < N; i++){
        ans = max(ans, DP[i]);
    }
    cout　<<　ans　<<　endl;
}

というふうになる. 0項が許容のときのコードは書いてみてください。

ここで \mathrm{DP}の参照が前の項にしかいかないことに着目すると, これは配列を用意する必要すらなくて(DP配列の次元を一次元落とすことができて),

int main(){
    vector<int> A = {-3, -1, 3, 8, 0, 2, -6, 8, -7, -1};
    int N = A.size();
    int sum = 0, ans = 0;
    for(int i = 0; i < N; i++){
    // 項数0が許容されていないなら,
    // int sum = A[0], ans = A[0];
    // for(int i = 1; i < N; i++){
        sum = max(sum + A[i], A[i]);
        ans = max(ans, sum);
    }
    cout　<<　ans　<<　endl;
}

というふうになる. 実際に実行すると

g++ main.cpp
./a.out
15

という結果を得ることができる.

これを見ると配列AのN個の要素に一度ずつアクセスしているので時間計算量は O(N) となることが確認できる.

例題

https://atcoder.jp/contests/arc174/tasks/arc174_a
https://leetcode.com/problems/maximum-subarray/description/
https://leetcode.com/problems/maximum-product-subarray/description/
https://leetcode.com/problems/maximum-sum-circular-subarray/description/
https://leetcode.com/problems/maximum-absolute-sum-of-any-subarray/description/

最後に

初めてKadane's Algorithmを使う問題に出会った時、こういう実装をしたいということは思いついたのですがそれをうまく実装することができなかったのを覚えています。同じ悩みを持った人がこの記事を読んで救われたら幸いです。ここまで読んでくれてありがとうございました✨✨
わかりにくかったり、間違っている部分があったらぜひ教えてください！
そういえば、"カダネ"じゃなくて"カデイン"って読むとか読まないとか(真偽不明)

Discussion