Pythonアルゴリズム

カダネのアルゴリズムで最大部分配列を求める

このレッスンでは、カダネ(Kadane)のアルゴリズムを使い、配列を1回たどるだけで合計が最大になる連続した区間を見つけます。

  • 中級
  • 約2分で読めます
  • 実行できるサンプル 1 件

はじめに

どんな問題を解決するか

株にとって最高の期間はいつか、得点で見た最長の連勝はどこか、旅行で最も利益の出た区間はどこか。これらはすべて最大部分配列の問題です。すべての始点と終点を調べると遅いですが、Kadane のアルゴリズムなら1回通るだけで解けます。

身近なたとえ

Kadane のアルゴリズムは、金を拾いながら通行料を払って道を歩くようなものです。今の区間の財布を持ち歩きます。財布がマイナスになったら持ち続けても損なだけなので、捨てて新しく始めます。これまででいちばん中身の多かった財布も覚えておきます。

有料道路からコードへ
current = max(value, current + value)👛 財布を持ち続けるか、悪ければ新しく始める
best = max(best, current)🏆 これまでで最も中身の多い財布を覚える
current = best = values[0]🚩 最初の区間から始める
6💰 最高の区間:4、-1、2、1
得になる間は区間を伸ばし、ならなければやり直します。
ひと言でいうと

最大部分配列問題は、リストの連続した要素の和の最大値を求めます。Kadane のアルゴリズムは各位置で終わる最良の和を追いかけることで、O(n) の時間で解きます。

重要なポイント

  1. current は、今の値で終わる区間の最良の和です。
  2. current = max(value, current + value) は、古い区間が和を下げるだけなら新しい区間を始めます。
  3. best = max(best, current) はどこかで見た最良の和を保ちます。
  4. 両方を values[0] から始めるので、負の数だけのリストでも動きます。

どんな場面で使う?

  • 利益、点数、気温など、時系列での最良の期間。
  • 1回通るだけの典型的な動的計画法の考え方を学ぶ。
  • 配列に関する面接問題。

使わなくてよいとき

  • 最良の区間の始まりと終わりが必要な場合:和だけでなく位置も追いかけます。
  • 値に意味のある順番がない場合:連続した区間には意味がありません。

サンプルコード

コードを実行 →
main.py
def maximum_subarray_sum(values):
    current = best = values[0]
    for value in values[1:]:
        current = max(value, current + value)
        best = max(best, current)
    return best

print(maximum_subarray_sum([-2, 1, -3, 4, -1, 2, 1, -5, 4]))
この例の実行ボタンを作成

実行結果

6

コードの解説

各要素で、変数currentは2つの選択肢から大きいほうを選びます。その要素から新しい区間を始めるか、current + valueで前の区間を続けるかです。変数bestはこれまでで最大の合計を保存します。サンプルデータでは区間[4, -1, 2, 1]の合計6が最大です。アルゴリズムはO(n)で動き、メモリはO(1)しか使いません。

値を変更し、PythonをインストールせずにCodeUtilityオンラインPythonコンパイラで実行できます。

発展問題

下のヒントにしたがってコードを書き換えてみましょう。自分で変えて結果を確かめると、コードを読むだけよりずっと深く理解できます。

  1. 空のリスト、要素が1つだけのリスト、重複した値を含むリストで試す。
  2. 各ステップの後の状態を表示して、アルゴリズムの動きを観察する。
  3. 要素が100個、1,000個、10,000個のときの実行時間を測り、別の解き方と比べる。
Pythonコンパイラで実行 →

よくある間違い

0から始める

すべて負の入力だと、答えが誤って0になります。

問題
current = best = 0
修正
current = best = values[0]

このレッスンを終えましたか?

学習済みにすると進み具合を記録できます。

チャレンジで練習する

このレッスンの内容を使って実際の問題を解きましょう。各チャレンジはブラウザで動き、すぐにテストされ、AI のレビューも受けられます。

すべてのチャレンジ