Kadaneのアルゴリズムで最大部分配列問題を解くPythonプログラム

Kadane（カデイン）のアルゴリズムを使って最大部分配列（Maximum Subarray）を求めたい場合、部分配列の最大値を見つけるための専用メソッドを定義します。そして、イテレーション（繰り返し処理）を通じて最大部分配列を追跡していきます。

以下に具体的な実装例を示します。

サンプルコード

def find_max_sub_array(my_list, beg, end):
    max_end_at_i = max_seen_till_now = my_list[beg]
    max_left_at_i = max_left_till_now = beg
    max_right_till_now = beg + 1
    for i in range(beg + 1, end):
        if max_end_at_i > 0:
            max_end_at_i += my_list[i]
        else:
            max_end_at_i = my_list[i]
            max_left_at_i = i
        if max_end_at_i > max_seen_till_now:
            max_seen_till_now = max_end_at_i
            max_left_till_now = max_left_at_i
            max_right_till_now = i + 1
    return max_left_till_now, max_right_till_now, max_seen_till_now

my_list = input('Enter the list of numbers... ')
my_list = my_list.split()
my_list = [int(x) for x in my_list]
beg, end, max_val = find_max_sub_array(my_list, 0, len(my_list))
print('The maximum subarray begins at index {}, ends at index {}'
      ' and its sum is {}.'.format(beg, end - 1, max_val))

実行結果

Enter the list of numbers... 2 5 7 12 6 8
The maximum subarray begins at index 0, ends at index 5 and its sum is 40.

コードの解説

• まず、「find_max_sub_array」という名前のメソッドを定義し、3つの引数（リスト、開始インデックス、終了インデックス）を受け取ります。

• このメソッドは、指定された範囲内における最大部分配列を求めます。

• 戻り値はタプル形式で、最大部分配列の左端・右端のインデックスと、その合計値が返されます。

• forループを使い、「インデックスiで終わる部分配列」の最大値を常にチェックします。

• この値こそが、すべての部分配列の中で最大のものとなります。

• また、ループが左端・右端のインデックスを走査する間、それまでに見つかった部分配列の最大合計も同時に記録していきます。

• メソッドの外側では、ユーザーから数値のリストを入力として受け取ります。

• 受け取ったリストは引数としてメソッドに渡されます。

• 最後に、計算結果がコンソールへ出力されます。

Kadaneのアルゴリズムのポイント

Kadaneのアルゴリズムは動的計画法（DP）の考え方に基づいた手法で、「現在位置で終わる部分配列の最大和」を順次更新しながら全体の最大値を求めます。全ての部分配列を総当たりで調べる方法（O(n²)やO(n³)）と比べ、線形時間O(n)で効率的に解ける点が大きな特徴です。負の数が含まれる配列にも対応でき、実務でも頻出する古典的なアルゴリズムの一つです。