[競プロ][Max Subarray] Kadane’s Algorithm解説

最大部分配列問題を解くとよく目にするKadane’s Algorithm
コードを見てもイマイチ動きをイメージしづらく、日本語での解説も少ないと思ったのでまとめてみる。

考え方

まずKadane’s AlgorithmはDynamic Programming問題と考えると理解しやすい。
前提として整数を要素にもつ配列をAとする。

DP[i]をAにおけるi以下の任意の要素(A[0]...A[i-1])から要素i(A[i])までの部分配列における和の最大値と定義する。(最初の要素から要素iまでの最大値ではないことに注意)
すると初期状態と状態遷移は下記のようになる。

• 初期状態：DP[0] = A[0]
• 状態遷移：DP[i+1] = max(A[i+1], DP[i]+A[i+1])
  (意味：DP[i+1]はA[i+1]もしくはDP[i]にA[i+1]を足したもの)

このときDP[n-1]が答えになるわけでなく、DP[0]...DP[n-1]の中での最大値が答えとなる。

文章での説明

下記の配列Aを考える。
[1, 2, 3, -4, -5, 6]

配列[1,2]の最大部分配列和は3である。
次に[1,2,3]の部分配列和を考えると候補は下記の3種類となる。

• [1,2,3]
• [2,3]
• [3]

しかし[1,2]の最大部分配列和は3と既にわかっているので実際に比較すべきものは下記に絞られる。

1. [1,2]の最大部分配列和と3の和
2. 3のみ

2は[1,2]の最大部分配列和が負の数になるときに選択される。

このアルゴリズムのポイントは各イテレーションでは要素iより前の要素のみを見ればいいということ。
それ以降の要素は次のイテレーション(i+1)以降で検証されるため。

練習問題

下記の問題を解いてみる。
1つ前の状態のみ覚えておけばいいのでDP配列を使わずsum変数のみで対応

53. Maximum Subarray

int maxSubArray(vector<int>& nums) {
    int sum = nums[0];
    int ans = sum;
    for (int i=1; i<nums.size(); i++) {
        int num = nums[i];
        sum = max(sum+num, num);
        ans = max(ans, sum);
    }    
    return ans;
}