Zenn
⛷️

Kadane’s Algorithm - Maximum subarray problem

2023/04/10に公開
競プロ
アルゴリズム
tech

アルゴリズムの問題をここ1年ほど解いているのですが、Kadane’s Algorithmというのを知ったので、というかまた間違えたので自身の復習も兼ねてアウトプットとして解説記事にします。

Maximum subarray problem

Maximum subarray problemとは次のようなシンプルな問題です：

次の１次元配列が与えられたとき

\mathrm{nums}[i] \in \mathbb{Z} \quad (0 \leq i \lt N)

この\mathrm{nums}の (連続した) 部分列の和で最大のものを求めよ

ex.
\mathrm{nums} = [-2,1,-3,4,-1,2,1,-5,4]のとき、部分列[4,-1,2,1]が最大の部分列の和 6 を与える

この解法としては直観的なBrute Forceの他に本記事で取り上げるKadane's Algorithmがあります。
計算量は以下のとおりです：

  • Brute Force: \mathcal{O}(N^2)
  • Kadane's Algorithm: \mathcal{O}(N)

直観的なBrute Forceに比較してなんと線形時間でできてしまうのが面白いですね。

Brute Force

まずはBrute Forceを考察してみましょう。
それぞれ部分列の最初と最後を考えて部分和を計算し、その最大値を記録します。

\mathrm{sum}[i:j] := \mathrm{nums}[i] + \mathrm{nums}[i+1] + ...+ \mathrm{nums}[j-1] \quad(i \lt j)

このアルゴリズムは\mathcal{O}(N^2)になります：

def brute_force(nums: List[int]):
    n = len(nums)
    max_sum = -inf
    for i in range(n):
        cur_sum = 0
        for j in range(i, n):
            cur_sum += nums[j]
            max_sum = max(max_sum, cur_sum)
    return max_sum

Intuition & Easy Proof

さてKadane's Algorithmを使えばこの計算が\mathcal{O}(N)で処理できます。
厳密な証明ではありませんがアイディアの核心を見たいと思います。
まず0から始まる区間の部分和を\mathrm{sum}[0:j]としてend jを１つずつ増やしていきましょう：

\mathrm{sum}[0:j] := \mathrm{nums}[0] + \mathrm{nums}[1] + ...+ \mathrm{nums}[j-1]

今 \mathrm{nums}[0] \geq 0 と仮定しても一般性を失いません。

\mathrm{sum}[0:j]の最大値を記録しながらjを増やしていき、0 < k を\mathrm{sum}[0:k]が負になる最小のindexと仮定します。(そんなkがない場合は容易)

もう0から始まる部分列の和をこれ以上考える必要はありません：

\mathrm{sum}[0:j] = \mathrm{sum}[0:k] + \mathrm{sum}[k:j] \lt \mathrm{sum}[k:j] \quad(k \lt j)

このとき次に考えるべき区間の最初のindexはどこでしょうか？

この答えがkであることが計算量が\mathcal{O}(N^2)から\mathcal{O}(N)に削減できるポイントとなります。
なぜならばl \lt kとして：

\begin{align*} \mathrm{sum}[l:j] &= \mathrm{sum}[l:k] + \mathrm{sum}[k:j] \\ &\le \mathrm{sum}[0:k] + \mathrm{sum}[k:j] \\ &\lt \mathrm{sum}[k:j] \end{align*}

よってl \lt kのとき\mathrm{sum}[l:j]が部分列の和で最大値となることはありません。次に考える部分列のstartのindexはkとなります。

Implementation

実装に際してもう１点注意しなければならないのは、全要素が負 i.e. 任意のiに対して\mathrm{nums}[i] < 0であるケースです。この場合は最大の要素を返すようにします。
Pythonによる実装は以下の通りです:

def kadane(nums: List[int]):
    cur_sum = max_sum = nums[0]
         
    for n in nums[1:]:
        cur_sum = max(cur_sum+n, n)
        max_sum = max(max_sum, cur_sum)
    return max_sum

Reference

Problems

情報求む

LeetCode

AtCoder

Other

Discussion