Alt toplamı en az

Question

bulmak için üretken özyineleme Python'da bir yineleme yineleme sorunu çözmeye çalışıyorum. Soru şu:

tamsayılar oluşan bir listede

• , büyük toplamı sahip bitişik alt listesini bulup bu toplamı dönün.
• Örneğin, verilen liste [−2, 1, −3, 4, −1, 2, 1, −5, 4] ise, en büyük toplamı olan bitişik alt liste [4, −1, 2, 1] bir toplamı olan 6

I find_max çözmek için verilen bir algoritmayı takip etmek zorunda: (orta noktasında)

1. Bölünmüş verilen liste ikiye: L_left ve L_right.
2. geri 3 Aşağıdaki maksimum değeri:
   • herhangi bir alt liste maksimum toplam L_left tamamen bulunur (find_max için yinelemeli çağrı ile).
   • Herhangi bir alt listenin maksimum toplamı tamamen L_right'da bulunur (find_max için tekrarlamalı bir çağrı kullanarak).
   • L_left ve L_right ile üst üste gelen maksimum alt liste; yani
     • İlk: (sola doğru) orta noktasından başlayan ve orta nokta
     • İkinci solunda bir noktada biten herhangi alt liste maksimum toplamını bul: başlayarak herhangi alt liste maksimum toplamını bul orta nokta (doğru doğru) ve orta noktanın sağında bir noktada biten
     • Son olarak: İki maksimum toplamı ekleyin.

Aşağıdaki denedim:

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 

bu özelliktir fazla unsurları ile bir liste için çalışmaya uzatmak nasıl uzunluğu 2 ile listelerin çözebilecek mi?

Answer 1

Aşağıdaki düşünün:

• başka temel durum: L []
• sol yarım ve sağ yarım ardışık olmalıdır olduğunu. L[2, -5, 3] ise
  • sizin koduna göre, ilk özyinelemede, left + right döngü olmadan 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 

---

verecektir:

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