查找最大总和子列表和总结分而治之

所以我试图打印最大总额以及其相应的子列表，但我无法弄清楚如何得到它的子列表。这里是我到目前为止的代码使用Python，只有返回最大总和：查找最大总和子列表和总结分而治之

full = [7,-1,1,2,-8,1] 
indices = [] 

def sumHelper(listnum, a, z): 
    if a == z: 
     global indices 
     return listnum[a] 
    mid = (a+z)//2 
    return max(sumHelper(listnum,a,mid),sumHelper(listnum,mid+1,z),straddleSum(listnum,a,mid,z)) 


def straddleSum(listnum, a, m, z): 
    right = -(2**31)-1 
    left = -(2**31)-1 
    count = 0 
    for i in range(m,a-1,-1): 
     count = count + listnum[i] 
     if count > left: 
      left = count 

    count = 0 
    for i in range(m+1,z+1): 
     count = count + listnum[i] 
     if count > right: 
      right = count 

    return right + left 

print(sumHelper(full, 0, len(full)-1)) 
print(indices)

来源

2017-10-07 catpuccino

任何示例i/p和预期的o/p？ – Transhuman

输入：[7，-1,1,2，-8,1] 输出：9 [7 -1 1 2] – catpuccino

嗨@catpuccino，请编辑您的代码，使其更清晰。 strsddleSum中的一些内容：函数的for循环（s）部分或不是。如果他们请妥善缩进代码。在另一个说明中，在sumHelper中，你有全局索引，但是在任何函数中你都没有做任何事情......如果是这样的话，最好把它拉出来。即使你操纵索引，更好的方法是将它作为参数传递给需要它的函数。 –

你只返回一个范围的总和。要获得范围，只需返回总和和范围的元组，而不仅仅是总和：return listnum[a], (a,z)。然后给max一个关键函数，所以它只使用元组中的和来找到最大范围key= lambda x: x[0]。

full = [7,-1,1,2,-8,1] 
# full = [-1,-2,-3,-4] 
# full = [1,2,-100,3,4] 
indices = [] 

def sumHelper(listnum, a, z): 
    if a == z: 
     global indices 

     # return sum of range and it's left and right index 
     return listnum[a], (a,z) 
    mid = (a+z)//2 
    return max(sumHelper(listnum,a,mid),sumHelper(listnum,mid+1,z),straddleSum(listnum,a,mid,z), key= lambda x: x[0]) 


def straddleSum(listnum, a, m, z): 
    right = -(2**31)-1 
    left = -(2**31)-1 

    lpos = rpos= None # left and right index of max range 

    count = 0 
    for i in range(m,a-1,-1): 
     count = count + listnum[i] 
     if count > left: 
      left = count 
      lpos = i 

    count = 0 
    for i in range(m+1,z+1): 
     count = count + listnum[i] 
     if count > right: 
      right = count 
      rpos = i 

    # return sum of range and it's left and right index 
    return right + left, (lpos, rpos) 

msum, msumb_range = sumHelper(full, 0, len(full)-1) 
print(msum) 
print(msumb_range)

来源

2017-10-07 05:04:10 Anonta

查找最大总和子列表和总结分而治之

回答

相关问题