[Python] Kadane’s algorithm

最大部分配列問題

数値で構成された配列内の部分配列の中で、総和が最大となるものを求めます。

In computer science, the maximum sum subarray problem is the task of finding a contiguous subarray with the largest sum, within a given one-dimensional array A[1…n] of numbers.

From Wikipedia, the free encyclopedia

配列の要素が全て負であれば、その中で一番大きい要素が回答になります。

配列の要素が全て正であれば、全ての要素の和が回答になります。

配列の中に正と負が混在していると、問題が難しくなります。

例えば、[2, 3, -1, -20, 5, 10] という配列を考えます。

最大となる部分配列は [5, 10] で、総和は 15 です。

単純に総当たりで考えると、以下のようなコードになります。

def maximum_subarray_BF(array):

    best_sum = float('-inf')
    best_start = best_end = -1

    for i in range(len(array)):
        for j in range(i+1, len(array)):
            current_sum = sum(array[i:j+1])
            if current_sum > best_sum:
                best_sum = current_sum
                best_start = i
                best_end = j

    return best_sum, (best_start, best_end)


if __name__ == '__main__':
    array = [2, 3, -1, -20, 5, 10]
    # (15, (4, 5))
    print(maximum_subarray_BF(array))

総当たりの計算量は\( O (N^2) \) です。

Kadane’s algorithm は、 この問題を \( O (N) \) で解くアルゴリズムです。

Kadane’s algorithm

動的計画法です。

current_max を現在考えている部分配列の最大値、best_max を求める部分配列の最大値と考えると、current_max = max(array[i], current_max+array[i]、best_max = max(best_max, current_max)として更新することができます。

Dynamic Programming – Kadane’s Algorithm

def maximum_subarray_kadane(array):

    best_sum = float('-inf')
    best_start = best_end = -1
    current_sum = 0

    for current_end, num in enumerate(array):
        if current_sum <= 0:
            current_start = current_end
            current_sum = num
        else:
            current_sum += num

        if current_sum > best_sum:
            best_sum = current_sum
            best_start = current_start
            best_end = current_end
    
    return best_sum, (best_start, best_end)


if __name__ == '__main__':
    array = [2, 3, -1, -20, 5, 10]
    # (15, (4, 5))
    print(maximum_subarray_kadane(array))