生成递归以查找具有最大总和的子列表

Question

我试图解决Python中的生成递归问题.问题是:

• 在由整数组成的列表中,找到具有最大总和并返回该总和的相邻子列表.
• 例如,如果给定列表是[-2,1,-3,4,-1,2,1,-5,4],则具有最大总和的相邻子列表为[4,-1,2,1] ],总和6

我必须按照给定的算法来解决find_max:

1. 将给定列表(中点)拆分为两个:L_left和L_right.
2. 返回以下3的最大值:
   • 任何子列表的最大总和完全驻留在L_left中(使用对find_max的递归调用).
   • 任何子列表的最大总和完全驻留在L_right中(使用对find_max的递归调用).
   • 与L_left和L_right重叠的最大子列表; 即
     • 第一:找到从中点(向左)开始到中点左侧某点的任何子列表的最大总和
     • 第二步:找到从中点(向右)开始到中点右侧某点的任何子列表的最大总和
     • 最后:添加两个最大值.

我尝试过以下方法:

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 是 []
• 左半部和右半部应该是连续的。
  • 根据你的代码， if Lis [2, -5, 3]，在第一次递归中，left + right将产生 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

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