分割統治法で最大部分配列問題を解くPythonプログラムの実装方法

本記事では、分割統治法（Divide and Conquer）を用いて最大部分配列問題（Maximum Subarray Problem）を解くPythonプログラムを紹介します。最大部分配列問題とは、配列内の連続する要素の合計が最大となる部分配列を見つける古典的なアルゴリズム問題です。

以下に、実際の実装例を示します。

サンプルコード

def max_crossing_sum(my_array, low, mid, high):

    sum_elements = 0
    sum_left_elements = -10000

    for i in range(mid, low-1, -1):
        sum_elements = sum_elements + my_array[i]

        if (sum_elements > sum_left_elements):
            sum_left_elements = sum_elements

    sum_elements = 0
    sum_right_elements = -1000
    for i in range(mid + 1, high + 1):
        sum_elements = sum_elements + my_array[i]

        if (sum_elements > sum_right_elements):
            sum_right_elements = sum_elements

    return max(sum_left_elements + sum_right_elements, sum_left_elements, sum_right_elements)

def max_sub_array_sum(my_array, low, high):

    if (low == high):
        return my_array[low]

    mid = (low + high) // 2

    return max(max_sub_array_sum(my_array, low, mid), max_sub_array_sum(my_array, mid+1, high), max_crossing_sum(my_array, low, mid, high))

my_list = [23, 12, 45, 67, 89, 11]
list_length = len(my_list)
print("The list is :")
print(my_list)

max_sum = max_sub_array_sum(my_list, 0, list_length-1)
print("The maximum contiguous sum is ")
print(max_sum)

出力結果

The list is :
[23, 12, 45, 67, 89, 11]
The maximum contiguous sum is
247

コードの解説

• まず、「max_crossing_sum」という関数を定義します。この関数は、リストを中央で分割した際に境界をまたぐ部分配列の合計を計算します。

• 続いて、「max_sub_array_sum」関数が再帰的に呼び出され、すべての部分配列の合計を効率的に計算します。

• 関数の外側でリストを定義し、その内容をコンソールに表示します。

• len() 関数を使用して、リストの長さを取得します。

• 定義したリストとインデックス範囲を引数として渡し、最大部分配列の合計を計算する関数を呼び出します。

• 最後に、計算された最大連続合計値をコンソールに出力します。

計算量について

分割統治法を用いたこのアプローチの時間計算量は O(n log n) です。これは、すべての部分配列を総当たりで調べる全探索（O(n²)）よりも効率的な手法です。さらに、Kadaneのアルゴリズムを使えば O(n) で解くことも可能ですが、分割統治法はアルゴリズムの基礎を学ぶ上で非常に重要な考え方となります。