6

Python で生成再帰の問題を解決しようとしています。質問は：

  • 整数で構成されるリストで、最大の合計を持つ隣接するサブリストを見つけ、その合計を返します。
  • たとえば、指定されたリストが [−2, 1, −3, 4, −1, 2, 1, −5, 4] の場合、合計が最大の隣接するサブリストは [4, −1, 2, 1] です。 ]、合計は 6

find_max を解決するには、指定されたアルゴリズムに従う必要があります。

  1. 指定されたリスト (中間点) を L_left と L_right の 2 つに分割します。
  2. 次の 3 つの最大値を返します。
    • サブリストの最大合計は、完全に L_left にあります (find_max への再帰呼び出しを使用)。
    • サブリストの最大合計は、完全に L_right にあります (find_max への再帰呼び出しを使用)。
    • L_left と L_right をオーバーラップする最大のサブリスト。つまり、
      • 最初: 中間点から (左に向かって) 開始し、中間点の左側のある点で終了するサブリストの最大合計を見つけます。
      • 2番目：中間点から（右に向かって）開始し、中間点の右側のある点で終了するサブリストの最大合計を見つけます
      • 最後に: 2 つの最大合計を追加します。

私は次のことを試しました：

def find_max(L):
    length = len(L)
    mid_index = length/2
    if length == 1:
        return L[0]
    else:
        left = find_max(L[0:(length/2)])
        right = find_max(L[(length/2):length])
        max_subset = max(left,right,left+right)
        return max_subset

これは、長さ 2 のリストを解決できます。これを拡張して、より多くの要素を持つリストを処理するにはどうすればよいですか?

4

1 に答える 1

2

あなたは次のことを考慮していませんでした：

  • 別の基本ケース: L は []
  • 左半分と右半分は連続している必要があります。
    • あなたのコードによると、最初の再帰でif Lis は5 になります。[2, -5, 3]left + right
def find_max(L):
    length = len(L)
    mid_index = length/2
    if length == 0:
        return 0
    elif length == 1:
        return max(L[0], 0)

    left = find_max(L[:mid_index])
    right = find_max(L[mid_index:])

    left_half = right_half = 0
    # to the left
    accum = 0
    for x in L[mid_index-1::-1]:
        accum += x
        left_half = max(left_half, accum)

    # to the right
    accum = 0
    for x in L[mid_index:]:
        accum += x
        right_half = max(right_half, accum)

    return max(left, right, left_half + right_half)


assert find_max([]) == 0
assert find_max([-1]) == 0
assert find_max([1, 2, 3]) == 6
assert find_max([2, -5, 3]) == 3
assert find_max([-5, 1, 4, -2, 2, -1, 2, -3, 1, -3, 4]) == 6

for ループなし:

def sum_max(L, accum=0, max_value=0):
    if not L:
        return max_value
    accum += L[0]
    return sum_max(L[1:], accum, max(max_value, accum))

def find_max(L):
    ...
    left_half = sum_max(L[mid_index-1::-1])
    right_half = sum_max(L[mid_index:])
    ...
于 2013-07-09T08:26:56.360 に答える