カダネのアルゴリズムで最大部分配列を求める
このレッスンでは、カダネ(Kadane)のアルゴリズムを使い、配列を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) の時間で解きます。
重要なポイント
currentは、今の値で終わる区間の最良の和です。current = max(value, current + value)は、古い区間が和を下げるだけなら新しい区間を始めます。best = max(best, current)はどこかで見た最良の和を保ちます。- 両方を
values[0]から始めるので、負の数だけのリストでも動きます。
どんな場面で使う?
- 利益、点数、気温など、時系列での最良の期間。
- 1回通るだけの典型的な動的計画法の考え方を学ぶ。
- 配列に関する面接問題。
使わなくてよいとき
- 最良の区間の始まりと終わりが必要な場合:和だけでなく位置も追いかけます。
- 値に意味のある順番がない場合:連続した区間には意味がありません。
サンプルコード
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つだけのリスト、重複した値を含むリストで試す。
- 各ステップの後の状態を表示して、アルゴリズムの動きを観察する。
- 要素が100個、1,000個、10,000個のときの実行時間を測り、別の解き方と比べる。
よくある間違い
0から始める
すべて負の入力だと、答えが誤って0になります。
current = best = 0
current = best = values[0]
このレッスンを終えましたか?
学習済みにすると進み具合を記録できます。
チャレンジで練習する
このレッスンの内容を使って実際の問題を解きましょう。各チャレンジはブラウザで動き、すぐにテストされ、AI のレビューも受けられます。
- Sliding Window Maximum Report the maximum of every window of k numbers. 難しい
- Largest Adjacent-Digit Product Take every contiguous window of span digits and multiply its digits. 中級