配列で複数の整数が与えられた時に和が最も大きくなる範囲とその和を求めるアルゴリズムについて

Question

前提・実現したいこと

配列で複数の整数が与えられた時に和が最も大きくなる範囲とその和を求めるプログラムを書いています。

例えば

A = [18, -10, 30, 23, -26, 37, 48, -19, -13, 31]
なら
112, 2, 6

発生している問題・エラーメッセージ

出力は出ていて、for文も回っているようなので何が問題なのか修正方法がわからず困っています。

現行のコードの出力

(119, 0, 0)

{30, 23, -26, 37, 48}の範囲で i = 2, j = 6なので、出力としては以下が正しいと考えられます。

112, 2, 6

該当のソースコード

def solution(A):
	start = 0
	end = len(A)
	max_total = 0
	tmp = 0
	for i in range(len(A)): 
		for j in range(len(A)-1, i-1, -1):
			tmp += A[j]
			if max_total < tmp:
				max_total = tmp
				start = i
				end = j
		tmp = 0
	return max_total, start, end

if __name__ == '__main__':
	A = [18, -10, 30, 23, -26, 37, 48, -19, -13, 31]
	ans = solution(A)
	print(ans)

補足情報（FW/ツールのバージョンなど）

Python 3.6

Comments

[torisan]

結果が119になるに当たって何を足しているか、追っていってみてはどうでしょうか？
想定より大きいという事は、明らかに無駄な部分があるという事ですし。

[tiitoi]

A[0:7] = {18, -10, 30, 23, -26, 37, 48} の 120 が最大ではないでしょうか？

[otolab]

（完全に余談）
あ、これO(n)で解けるって言われませんでした？この問題、懐かしい。

[退会済みユーザー]

ご指摘とコメントをありがとうございます。
O(n)で解けるとはどういうことでしょうか。現行のプログラムだと55回探索をしていますが、n+(n-1)+(n-2)+....+2+1で結局オーダ記法にするとO(n)ということでしょうか。

[退会済みユーザー]

もしご存知でしたらこの問題の名称も教えていただけると幸いです。

[jun68ykt]

otolabさんの余談に乗っかって、O(n)で解を求めるコードを追記しました。たぶん、追記のコードでうまくいくのではないかと思ってますが、おかしかったらご指摘ください。

[otolab]

jun68ykt すごい早いｗ
自分も一応は解けたのですが、もっとややこしく考えてしまって時間がかかった覚えがあります。

Answer 1

全探索でやる場合は以下のように範囲の始点 i に対して、i + 1 ~ 末尾までの終点の和を計算すればよいと思います。
和の計算は for 文を回すのではなく、組み込み関数 sum() を使いましょう。

def solution(lst, verbose=False):
    max_total = min(lst) - 1  # 必ず1回は if 文が実行される値を初期値としておく。

    total = 0
    for i in range(len(lst)):
        for j in range(i + 1, len(lst) + 1):
            total = sum(lst[i:j])
            if verbose:  # デバッグ用
                print(f"lst[{i}:{j}] = {lst[i:j]}, sum = {total}")

            if max_total < total:
                max_total = total
                start = i
                end = j
    return max_total, start, end


lst = [18, -10, 30, 23, -26, 37, 48, -19, -13, 31]
print(solution(A, True))

(120, 0, 7)

lst[0:1] = [18], sum = 18
lst[0:2] = [18, -10], sum = 8
lst[0:3] = [18, -10, 30], sum = 38
lst[0:4] = [18, -10, 30, 23], sum = 61
lst[0:5] = [18, -10, 30, 23, -26], sum = 35
lst[0:6] = [18, -10, 30, 23, -26, 37], sum = 72
lst[0:7] = [18, -10, 30, 23, -26, 37, 48], sum = 120
lst[0:8] = [18, -10, 30, 23, -26, 37, 48, -19], sum = 101
lst[0:9] = [18, -10, 30, 23, -26, 37, 48, -19, -13], sum = 88
lst[0:10] = [18, -10, 30, 23, -26, 37, 48, -19, -13, 31], sum = 119
lst[1:2] = [-10], sum = -10
lst[1:3] = [-10, 30], sum = 20
lst[1:4] = [-10, 30, 23], sum = 43
lst[1:5] = [-10, 30, 23, -26], sum = 17
lst[1:6] = [-10, 30, 23, -26, 37], sum = 54
lst[1:7] = [-10, 30, 23, -26, 37, 48], sum = 102
lst[1:8] = [-10, 30, 23, -26, 37, 48, -19], sum = 83
lst[1:9] = [-10, 30, 23, -26, 37, 48, -19, -13], sum = 70
lst[1:10] = [-10, 30, 23, -26, 37, 48, -19, -13, 31], sum = 101
lst[2:3] = [30], sum = 30
lst[2:4] = [30, 23], sum = 53
lst[2:5] = [30, 23, -26], sum = 27
lst[2:6] = [30, 23, -26, 37], sum = 64
lst[2:7] = [30, 23, -26, 37, 48], sum = 112
lst[2:8] = [30, 23, -26, 37, 48, -19], sum = 93
lst[2:9] = [30, 23, -26, 37, 48, -19, -13], sum = 80
lst[2:10] = [30, 23, -26, 37, 48, -19, -13, 31], sum = 111
lst[3:4] = [23], sum = 23
lst[3:5] = [23, -26], sum = -3
lst[3:6] = [23, -26, 37], sum = 34
lst[3:7] = [23, -26, 37, 48], sum = 82
lst[3:8] = [23, -26, 37, 48, -19], sum = 63
lst[3:9] = [23, -26, 37, 48, -19, -13], sum = 50
lst[3:10] = [23, -26, 37, 48, -19, -13, 31], sum = 81
lst[4:5] = [-26], sum = -26
lst[4:6] = [-26, 37], sum = 11
lst[4:7] = [-26, 37, 48], sum = 59
lst[4:8] = [-26, 37, 48, -19], sum = 40
lst[4:9] = [-26, 37, 48, -19, -13], sum = 27
lst[4:10] = [-26, 37, 48, -19, -13, 31], sum = 58
lst[5:6] = [37], sum = 37
lst[5:7] = [37, 48], sum = 85
lst[5:8] = [37, 48, -19], sum = 66
lst[5:9] = [37, 48, -19, -13], sum = 53
lst[5:10] = [37, 48, -19, -13, 31], sum = 84
lst[6:7] = [48], sum = 48
lst[6:8] = [48, -19], sum = 29
lst[6:9] = [48, -19, -13], sum = 16
lst[6:10] = [48, -19, -13, 31], sum = 47
lst[7:8] = [-19], sum = -19
lst[7:9] = [-19, -13], sum = -32
lst[7:10] = [-19, -13, 31], sum = -1
lst[8:9] = [-13], sum = -13
lst[8:10] = [-13, 31], sum = 18
lst[9:10] = [31], sum = 31
(120, 0, 7)

Comments

[退会済みユーザー]

ご回答いただきましてありがとうございます。
今後デバグの際は紹介いただいたように表示させて確認しようと思います。
組み込み関数 sum() を使った方が良い理由は計算速度でしょうか。

[tiitoi]

速度というより、コードの簡潔さですね。
C 言語であれば、質問のコードのように for で書きますが、Python は標準ライブラリが充実してるので、それを使って少ない行数でかけるなら利用したほうがよいかと思います。

Answer 2

こんにちは

はじめに題意の確認ですが、ご質問に

A = [18, -10, 30, 23, -26, 37, 48, -19, -13, 31]

として、

{30, 23, -26, 37, 48}の範囲で i = 2, j = 6なので、出力としては以下が正しいと考えられます。

112, 2, 6

とあったので、（上記自体は最大ではありませんが、）欲しい出力の形式は

(合計値の最大値, 合計が最大になる部分リストの開始インデクス, 合計が最大になる部分配列の終端インデクス)

という要素が3つのタプルで、合計が最大になる部分リストの終端インデクス も、合計の対象に含まれる　と解釈しました。以下、これを前提とした回答になります。

まず、ご質問に上げられているコードでは何が拙いかというと、合計の比較の際に、以下のようにしている箇所です。

for j in range(len(A)-1, i-1, -1):
       tmp += A[j]
       if max_total < tmp:

これだと、A の部分リストのうち、終端がAの終端と同じであるもの、すなわち 以下の10種類のリスト

• [31]
• [-13,31]
• ・・・
• [18, -10, 30, 23, -26, 37, 48, -19, -13, 31] (Aと同じ）

の要素の合計値を比較しています。
二重にループを回して、くまなく合計を比較しているように見えて、コードを追っていけば、比較対象となる合計値としては、上記の10種類のリストの合計値しか出てきません。

開始インデクスを i ( 0<=i<len(A) )とすると 終端インデクスの取り得る場合の数は len(A)-i 個　で 、いま len(A) は 10 なので、比較対象となる合計値は、重複を考慮しなければ（すなわち、異なる部分リストの要素の合計が(たまたま)一致してもそれらは個別に数えるとして、）

10+9+8+7+6+5+4+3+2+1 = 55 個

あるはずです。これを抑えたうえで、二重のループによって、合計を算出すべき部分リストが 55 種類出現しているかという観点で、見直されるとよいかと思います。

次に、具体的な修正案ですが、ご質問にあるコードをなるべく活かすとすると、たとえば以下のようになるかと思います。

def solution(A):
    start = None
    end = None
    max_total = 0

    for i in range(len(A)):
        for j in range(i, len(A)):
            tmp = sum(A[i:j+1])
            if max_total < tmp:
                max_total = tmp
                start = i
                end = j

    return max_total, start, end


if __name__ == '__main__':
    A = [18, -10, 30, 23, -26, 37, 48, -19, -13, 31]
    ans = solution(A)
    print(ans)

上記を実行すると

(120, 0, 6)

と表示されます。開始インデクス 0 、終端インデクス 6(※これも含む） であるAの部分リスト

[18, -10, 30, 23, -26, 37, 48]

の要素の合計値 120 が最大となることが分かります。
なお上記のコードでは、 A が空のリストであるとき、開始と終端が求められないことを表すために
(0, None, None)
を返すようにしています。

もうひとつ別解を以下に挙げます。

def solution(A):
    if len(A) == 0:
        return 0, None, None

    totals = sorted(
        [(sum(A[i:j+1]), i, j)
            for i in range(len(A))
            for j in range(len(A))
            if i <= j
         ],
        key=lambda x: x[0],
        reverse=True)

    return totals[0]


if __name__ == '__main__':
    A = [18, -10, 30, 23, -26, 37, 48, -19, -13, 31]
    ans = solution(A)
    print(ans)

上記で、 sorted の第1引数になる、内包表記によるリスト

[(sum(A[i:j+1]), i, j)
    for i in range(len(A))
    for j in range(len(A))
    if i <= j
]

は、以下のようなタプル

(部分リストの要素の合計値, 部分リストの開始インデクス, 部分リストの終端インデクス)

を、A の部分リストのすべてについて含み、このリストの長さは先に求めた、場合の数の 55 になります。

以上、参考になれば幸いです。

追記

すべての部分リストを調べなくても、以下で大丈夫かなと思います。

def solution(A):
    start = None
    end = None

    if len(A) == 0:
        return 0, start, end

    # 開始インデクスを求める
    start = 0
    tmp = 0
    for i in range(len(A)):
        tmp += A[i]
        if tmp <= 0 and i+1 < len(A):
            start = i+1

    # 終端インデクスを求める
    tmp = 0
    max_total = None

    for j in range(start, len(A)):
        tmp += A[j]
        if max_total is None or tmp > max_total:
            end = j
            max_total = tmp

    return max_total, start, end


if __name__ == '__main__':
    A = [-1, 5, -10, 9, -4, 18, -10, 30, 23, -26, 37, 48, -19, -13, 31]
    ans = solution(A)
    print(ans)

(120, 5, 11)

上記は二重のループがないので、 O(n) で済んでいます。

追記2

上記のコードが正解ではないことを、コメントからご指摘、ありがとうございます。
自分でやろうと思ったのですが、たぶんどこかに良質な回答のコードがあるだろうと思って調べましたところ、以下を見つけました。

• Stackoverflow: Maximum sum sublist? の回答

If you want the start and end slice indices, too, you need to track a few more bits of information (note this is still O(1) space and O(n) time, it's just a bit hairier):

def mssl(l):
    best = cur = 0
    curi = starti = besti = 0
    for ind, i in enumerate(l):
        if cur+i > 0:
            cur += i
        else: # reset start position
            cur, curi = 0, ind+1

        if cur > best:
            starti, besti, best = curi, ind+1, cur
    return starti, besti, best

上記に対して、

A = [-1, 5, -10, 9, -4, 18, -10, 30, 23, -26, 37, 48, -19, -13, 31]

を与えたサンプルを以下に作成しました。

• https://repl.it/@jun68ykt/Q192033

上記を実行すると

(3, 12, 125)

と表示されます。このコードの場合、 (開始, 終端, 合計)　を返しており、終端 は含まない形式で返してくれます。

Comments

[退会済みユーザー]

ご丁寧に説明いただきましてありがとうございます。大変わかりやすく、何が問題だったのかわかりました。

[jun68ykt]

どういたしまして。解決されたようでよかったです ????

[jun68ykt]

計算量が O(n) で済み、問題を（おそらく）解決するコードを追記しました。

A のインデクス 0 から始まる部分リストで、合計が0以下になる場合、その部分リストは、解となる部分リストから除外されるべき、という考えで、初めに開始インデクスを求めてから、次に終端を求めています。

これが分かるように、サンプルの A の先頭に要素を追加しています。

ちなみに、55 個の部分リストをくまなく調べるのは O(n^2) ですが、O(n) で済むものを O(n^2) で解くのは無駄なので、追記のほうを推奨します。

[can110]

最後のコードだとA=[-1,-2]の場合に(-2, 1, 1)と誤答してしまうようです。

[退会済みユーザー]

@jun68ykt ご丁寧に追記いただきましてありがとうございます。

１点解釈について念の為確認させていただきたいのですが、この解法は分割統治法（大きな問題を効率的に解く手法の一つで、問題全体を同じ構造の小さな問題に再帰的に分割していき、簡単に解けるサイズにした上で解いていく方式）ではないという理解で合っていますでしょうか。

分割統治法でも解けると聞いたのですが、分割統治法とアルゴリズムの理解がまだ乏しく、伺いました。
別の質問をすべき場合はご指摘願います。

[otolab]

> A = [-1, 5, -10, 9, -4, 18, -10, 30, 23, -26, 37, 48, -19, -13, 31]

A[3] + A[4] > 0なので、(125, 3, 11)になるはずです。
すんごい惜しいです。

> A = [18, -10, 30, 23, -26, 37, 48, -19, -13, 31]
> なら
> 112, 2, 6

設問もちょっと変で、A[0] + A[1] > 0なので、答えは(120, 0, 6)になるはずなんですが。

[otolab]

ちなみに、さっき思い出して書いてみたら、16行くらいになりました。

[jun68ykt]

@can110さん

> 最後のコードだとA=[-1,-2]の場合に(-2, 1, 1)と誤答してしまうようです。

ご指摘ありがとうございます。

@otolabさん

> すんごい惜しいです。

チェックいただき、ありがとうございます。

> A[3] + A[4] > 0なので、(125, 3, 11)になるはずです。

そうですかー、「左から足し込んで 0 以下の区間は捨てる」っていうのは駄目ですね。

後ほど出直します。。。

[jun68ykt]

@tenjinさん

>１点解釈について念の為確認させていただきたいのですが、この解法は分割統治法（大きな問題を効率的に解く手法の一つで、問題全体を同じ構造の小さな問題に再帰的に分割していき、簡単に解けるサイズにした上で解いていく方式）ではないという理解で合っていますでしょうか。

はい。少なくとも、大きい問題（このご質問でいえば A 全体）を再帰的に分割して、より小さい対象に対する問題に帰着させていくことはやっていないです。

昨日考える中で、
「再帰でもいけそうかな？」
とも思いましたが、昨日考えた中ではコードを書くに至りませんでした。。。

[jun68ykt]

@皆さま

stackoverflow に良さそうなコードをみつけたので回答に追記しました。こちらのコードを読んで、私も自身の浅学非才を猛省いたしたく。ありがとうございました。m(_ _)m

[退会済みユーザー]

@皆さま

質問は至らない部分が多くありましたが、大変深い議論をありがとうございました。多く学ばせていただきました。