Kadane法による最大部分配列
各位置で現在の区間を続けるか新しく始めるか判断します。
Kadane法による最大部分配列とは？
各位置で現在の区間を続けるか新しく始めるか判断します。
合計が最大となる連続区間を探します。
どのような場面で使う？
- アルゴリズムとデータ構造を理解する。
- 各ステップと境界ケースを確認する。
- 実行時間とメモリ使用量を比較する。
サンプルコード
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仕組み
1回の走査で求められ、時間O(n)、メモリO(1)です。
値を変更し、PythonをインストールせずにCodeUtilityオンラインPythonコンパイラで実行できます。
練習問題
入力値と境界ケースを変更し、より大きなデータでも動作を確認してください。
- 空入力、1要素、重複値を試す。
- 各ステップの状態を表示する。
- 別の解法と性能を比較する。