查找具有最大和的idx

Question

所以我需要写一个返回索引的递归程序，这样元素的和就是最大的。例如列表[1,-5,9,-12,3,3,3,2]，元素总和最大的idx是2。另一个例子:列表[1,-5,9,7]，在本例中返回的idx是3。如果有人知道怎么做，或者知道一个类似的问题，有人在论坛上问，这将是有帮助的。谢谢

Answer 1

您需要输入一个较低的总和估计值，这就是我使用min(list_of_numbers)*100的原因。您可能需要修改它，如果您可以使用numpy，我建议使用-np.inf替换该值

list_of_numbers = [1,-5,9,-12,3,3,3,2]

def maxSumId(list_of_numbers):
    id_max = 0
    sumVal = 0
    maxVal = min(list_of_numbers)*100
    for i,number in enumerate(list_of_numbers):
        sumVal += number
        if sumVal > maxVal:
            maxVal = sumVal
            id_max = i
    return id_max
    
maxSumId(list_of_numbers)

Answer 2

您的递归可以很容易地计算累积和，但它需要携带最大值及其索引，以便返回索引而不是值。

# L:list, i:current index, s:current sum, mi:max sum index, ms:max sum value

def iMaxSum(L,i=0,s=0,mi=0,ms=None):
    if i>=len(L): return mi           # end of list return max index
    if ms is None or L[i]+s>ms:       # track max sum and its index 
        ms,mi = s + L[i],i
    return iMaxSum(L,i+1,s+L[i],mi,ms) # next item,index,sum

    
print(iMaxSum([1,-5,9,-12,3,3,3,2])) # 2
print(iMaxSum([1,-5,9,7]))           # 3