最大総和を持つサブリストを見つけるための生成再帰

Question

私はPythonで生成的再帰問題を解決しようとしています。質問です：整数で構成されて一覧で

• 、 最大合計し、その合計を返すがあり、隣接するサブリストを見つけます。
• たとえば、指定されたリストが[-2、1、-3、4、-1,2,1,4,4]の場合、最も大きな合計を持つ隣接するサブリストは[4、-1、 2、1]、私はFIND_MAX解決するために与えられたアルゴリズムに従わなければならない合計6

有する：L_leftとL_right：二つに（中間点）のリストを与え

1. スプリット。
2. 戻り3以下の最大値：
   • 任意のサブリストの最大合計が（FIND_MAXする再帰呼び出しを使用して）L_leftで完全に常駐します。
   • サブリストの最大合計は、（find_maxへの再帰呼び出しを使用して）完全にL_rightに存在します。
   • L_leftおよびL_rightと重複する最大サブリスト。すなわち、
     • ファースト：（左方向）の中間点から始まり、途中
     • 第二の左にある時点 で終わる任意のサブリストの最大合計を探す：から始まるサブリストの最大合計を探します中点（ 右に向かって）中点の右のある点で終わる
     • 最後に、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でリストに解決することができますか？

Answer 1

あなたは以下の点を考慮しませんでした：

• 別のベースケース：Lは、[]
• 左半分と右半分が連続であるべきです。 Lが[2, -5, 3]ある場合
  • あなたのコードによると、最初の再帰では、left + rightは、forループなしで5

---

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 

---

が得られます：

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:]) 
    ...