0

整数のリストを取り、リストの最大合計サブリストを返す関数を作成する必要があります。例は次のとおりです。

l = [4,-2,-8,5,-2,7,7,2,-6,5]

戻り値19

これまでのところ、私のコードは次のとおりです。

count = 0
for i in range(0,len(l)-1):
    for j in range(i,len(l)-1):
        if l[i] >= l[j]:

            count += l[i:j]

return count

私は行き詰まって混乱しています。誰か助けてもらえますか? ありがとう！

4

3 に答える 3

0

これは「最大サブアレイ問題」と呼ばれ、線形時間で実行できます。ウィキペディアの記事にあなたの答えがあります。

于 2013-03-13T07:51:16.410 に答える
0

これは宿題だと思うので、ここでアルゴリズムをグーグルで検索したり、コードを投稿しすぎたりするつもりはありません。

いくつかのアイデア (頭のてっぺんから、「私はこの種のタスクが好きだから :-))」

ユーザー lc がすでに素朴で徹底的な方法を指摘しているように、すべてのサブリストをテストすることです。あなたの (user2101463) コードはその方向に進んでいると思います。sum()合計を構築し、既知のベストと比較するために使用するだけです。妥当な開始値で最もよく知られている合計を準備するには、リストの最初の値を使用します。

the_list = [4,-2,-8,5,-2,7,7,2,-6,5]

best_value = the_list[0]
best_idx = (0,0)
for start_element in range(0, len(the_list)+1):
    for stop_element in range(start_element+1, len(the_list)+1):
        sum_sublist = sum(the_list[start_element:stop_element])
        if sum_sublist > best_value:
            best_value = sum_sublist
            best_idx = (start_element, stop_element)

print("sum(list([{}:{}])) yields the biggest sum of {}".format(best_idx[0], best_idx[1], best_value))

もちろん、これには二次実行時間 O(N^2) があります。つまり、入力リストの要素数によって定義される問題のサイズが N で増加する場合、ランタイムは N*N で増加し、いくつかの任意の係数が使用されます。

改善のためのいくつかのヒューリスティック:

  • 達成可能な合計が減少するため、明らかに負の数は適切ではありません
  • 一連の負の数に遭遇した場合、これまでの最良のリストと負の数の合計が < 0 の場合は、その一連の後で最良のサブリストを再開します。例のリストでは、最初の 3 つの数値は最良のリストの一部になることはできません。のプラスの効果は、4によって常に打ち消されます-2, -8。
  • おそらくこれは、最初から最後まで反復するだけの実装につながりO(N)、最もよく知られている開始インデックスを記憶しながら、その開始インデックスからの完全な合計の実行中の合計と、正と負の数の最後の継続シーケンスの正と負の小計を計算します。 、 それぞれ。
  • このような最適なリストが見つかったら-6, 5、例の最後にあるような末尾の否定的なサブリストを削除するために、最終的なクリーンアップが必要になる可能性があります。

これが正しい方向につながることを願っています。

于 2013-02-25T14:13:55.213 に答える