sucesion sintaxis resueltos recursivo recursividad recursiva programacion programa potencia ejercicios python algorithm recursion sublist

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.

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:

  1. Dividir la lista dada (en el punto medio) en dos: L_left y L_right.
  2. 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?