查找具有最大总和的连续子集

Question

def max_sublist(x):
 max1 = 0
 max2 = 0
 result = []
 for i in x:
     max2 = max(0, max2 + i)
     max1 = max(max1, max2)

 print result

我想添加元素直到具有最大总和的元素.如何仅向结果添加其元素.

对于前者 如果x = [4, -1, 5, 6, -13, 2] 那么结果应该是[4, -1, 5, 6]

Answer 1

这是优化中的经典问题,它被称为最大子阵列问题.这是O(n)使用Kadane算法的一种可能的动态编程解决方案:

def max_val_contiguous_subsequence_idxs(seq):
    i = thisSum = maxSum = 0
    startIdx, endIdx = 0, -1
    for j in xrange(len(seq)):
        thisSum += seq[j]
        if thisSum > maxSum:
            maxSum = thisSum
            startIdx = i
            endIdx   = j
        elif thisSum < 0:
            thisSum = 0
            i = j + 1
    return (maxSum, startIdx, endIdx)

上面将在单个传递中返回一个元组,该元组具有子序列的最大值,起始索引和结束索引.例如,使用问题中的示例输入:

lst = [4, -1, 5, 6, -13, 2]
maxSum, startIdx, endIdx = max_val_contiguous_subsequence_idxs(lst)

maxSum
=> 14
lst[startIdx:endIdx+1]
=> [4, -1, 5, 6]

请注意,维基百科页面中显示的实现(看起来很像你想要的解决方案)只给出了最大值,但与我的解决方案不同,它们并没有告诉你如何在数组中找到子序列索引.