Đệ quy phát sinh để tìm danh sách con với số tiền tối đa

Question

Tôi đang cố gắng giải quyết một vấn đề đệ quy sinh ra trong Python. Câu hỏi là:

• Trong danh sách bao gồm các số nguyên, hãy tìm danh sách phụ liền kề có số tiền lớn nhất và trả lại số tiền đó. Ví dụ, nếu danh sách đã cho là [−2, 1, −3, 4, −1, 2, 1, −5, 4], danh sách phụ liền kề có tổng lớn nhất là 2, 1], trong đó có một số tiền 6

tôi phải làm theo các thuật toán được để giải quyết find_max:

1. Chia danh sách cho trước (ở điểm giữa) thành hai: L_left và L_right.
2. Trả lại giá trị tối đa sau đây: 3:
   • Tổng tối đa của bất kỳ danh sách con nào hoàn toàn nằm trong L_left (sử dụng cuộc gọi đệ quy đến find_max).
   • Tổng tối đa của bất kỳ danh sách con nào hoàn toàn nằm trong L_right (sử dụng cuộc gọi đệ quy đến find_max).
   • Danh sách phụ tối đa trùng lặp L_left và L_right; tức là,
     • đầu tiên: Tìm tổng max của bất kỳ sublist bắt đầu từ điểm giữa (về phía bên trái) và kết thúc tại một số điểm trên bên trái của trung điểm
     • Thứ hai: Tìm tổng max của bất kỳ sublist bắt đầu từ điểm giữa (về phía bên phải) và kết thúc tại một số điểm ở bên phải của điểm giữa
     • Cuối cùng: Thêm hai số tiền tối đa.

Tôi đã thử những điều sau đây:

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 

này có thể giải quyết cho các danh sách với chiều dài 2. Làm thế nào để mở rộng này để làm việc cho một danh sách với các yếu tố hơn?

Answer 1

Bạn đã không xem xét sau đây:

• một trường hợp cơ sở: L là []
• nửa trái và nửa bên phải nên liên tiếp.
  • Theo mã của bạn, nếu L là [2, -5, 3], trong đệ quy đầu tiên, left + right sẽ mang lại 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 

---

Nếu không có vòng lặp 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:]) 
    ...