Pythonで最大部分配列問題(maximum subarray problem)を解く #Python

はじめに

皆さん初めまして。ryuichi69と申します。

本日はアルゴリズムの勉強したもののアウトプットをここに書こうと思います。本日は最大部分配列問題(maximum subarray problem)というアルゴリズムを扱います。説明の分かりにくい部分、要件漏れ等がありましたらコメントにてご連絡下さい。

最大部分配列問題(maximum subarray problem)とは？

さて本題です。最大部分和問題とは、「各要素に整数が入った配列があり、そのうちいくつか選んだ時、その選んだものの合計の最大値を求めよ」と言う問題です。

問題

nを0以上の整数とします。このとき、n個の要素からなる数列(配列)a[k]が以下の条件をみたしています。

a[0],a[1],.....a[n-1]は整数
数列aの各要素は降順に並んでいるものとします。1≦i≦(n-1)を満たすすべての自然数iに対し、a[i] > a[i+1]をみたします。

さらに、kを1≦k≦nを満たす自然数とします。数列a[n]の要素のうち、任意のk個を選ぶ。このとき選んだものの内、その和が最大となるものをS[k]とするプログラムを作成してください。

制約

1≦n≦10
1≦k≦10
-10≦a[k]≦10

＊アルゴリズムの練習なので、計算量などは考慮しません。

入力1

a = [7,9,-1,1,-4]
k = 4
＊上記のようにa = [7,9,-1,1]と配列の要素が降順でない場合は、配列の要素を降順にソートして集計して下さい。

出力1

入力2

a = [-1,-2,-3,-4]
k = 3
＊要素が全て負の整数の場合は足し合わせません。

出力2

やり方(Kadane's algorithm)

配列1個1個に対し、0番から順々に足して行く。そして足した合計値が足す前より大きくなる場合、その値をS_kとして採用します。具体的には、

配列を降順にソートする
整数a,bの大きい方を返す関数max(a,b)を作る
kを1ずつ増やして行って、和の最大値s[k-1]にa[k]を足し合わせる場合、足しわせない場合をそれぞれ考え、値の大きい方をs[k]として配列にメモ(格納)していきます(動的計画法)。式に表すと、
- s[0] = max(a[0],0)
- s[k] = max(s[k-1] + a[k],s[k-1])

Pythonプログラム

solve.php

# a[i]の各要素を降順にならべるため、
# 一旦配列をバブルソートする
def bsort(arr):

    # 入れ替え用の
    temp = 0

    # 2重ループさせます{計算量はO(n^2)}
    for i in range(0,len(arr)-1):
        for j in range(0,len(arr)-1):
            # 今回は降順なので、一つ後の要素が現在の要素より
            # 大きい場合のみ入れ替えを行います
            if(arr[j] < arr[j+1]):
                temp = arr[j]
                arr[j] = arr[j+1]
                arr[j+1] = temp
    return arr

# 2つの整数a,bのうち、大きいものを返します
def max(a,b):
    if a > b:
        return a
    return b

def solve(arr,k):

    #　まず配列を降順にソートします
    b = bsort(arr)

    #　動的計画法(dp)より、各段階の合計値をメモします
    dp = [0] * len(arr)

    # dpを計算します{計算量はO(n)}
    for i in range(0,len(b)):
        # dp[0](初期値)を決定します
        if i == 0:
            # 配列の要素が0より大きい整数ならばb[0]
            # 配列の要素が0より小さい整数ならば0をdp[0]に採用します
            # バブルソートにより降順にソートされているので、b[0] < 0ならば
            # 以後全ての和dp[i]が0となります
            dp[0] = max(b[0],0)
        else:
            # dp[i-1]+b[i]>dp[i-1]の場合のみ、dp[i]に採用
            # それ以外の場合はdp[i-1]をdp[i]に採用
　　　　　　　# すみません。訂正しました(2019.12.29)
            dp[i] = max(dp[i-1]+b[i],dp[i-1])

    #　第二引数に対応するdp[k]を返す
    return dp[k-1]

#　テスト用
if __name__ == "__main__":
    a = [7,9,-1,1,-4]
    print(solve(a,4))

    b = [-1,-2,-3,-4]
    print(solve(b,3))

参考

Ark's Blog | Kadane’s Algorithm | 最大部分配列問題
 Qiita | C#でアルゴリズムとデータ構造1 ～最大部分配列問題～