python - sintaxis - Recursión generativa para encontrar la sublista con la suma máxima
sintaxis de recursividad (1)
No considerabas seguir:
- otro caso base: L es []
- la mitad izquierda y la mitad derecha deben ser consecutivas.
- Según su código, si
L
es[2, -5, 3]
, en la primera recursión,left + right
dará 5.
- Según su código, si
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
Sin para bucle:
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:])
...
Estoy tratando de resolver un problema de recursión generativa en Python. La pregunta es:
- En una lista que consta de enteros, encuentre la sublista contigua que tenga la suma más grande y devuelva esa suma.
- Por ejemplo, si la lista dada es [-2, 1, -3, 4, -1, 2, 1, -5, 4], la sublista contigua que tiene la suma más grande es [4, -1, 2, 1 ], que tiene una suma 6
Tengo que seguir el algoritmo dado para resolver find_max:
- Dividir la lista dada (en el punto medio) en dos: L_left y L_right.
- Devuelve el valor máximo de 3 siguientes:
- La suma máxima de cualquier sublista reside completamente en L_left (usando una llamada recursiva a find_max).
- La suma máxima de cualquier sublista reside completamente en L_right (usando una llamada recursiva a find_max).
- La sublista máxima que se superpone con L_left y L_right; es decir,
- Primero: Encuentre la suma máxima de cualquier sublista comenzando desde el punto medio (hacia la izquierda) y terminando en algún punto a la izquierda del punto medio
- Segundo: Encuentre la suma máxima de cualquier sublista comenzando desde el punto medio (hacia la derecha) y terminando en algún punto a la derecha del punto medio
- Finalmente: agregue las dos sumas máximas.
He probado lo siguiente:
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
Esto es capaz de resolver listas con longitud 2. ¿Cómo extiendo esto para trabajar en una lista con más elementos?