查找具有最大和的连续子集 [英] finding contiguous Subset with Largest Sum

问题描述

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

 print result

我想添加元素直到具有最大和的元素。我该如何只将其元素添加到结果中。

I want to add elements till the element which had the max sum. How do I add only whose elements to the result.

例如如果 x = [4，-1，5，6，-13，2]
，则结果应为 [4，-1 ，5，6]

推荐答案

这是优化过程中的经典问题，称为<一个href = http://en.wikipedia.org/wiki/Maximum_subarray_problem rel = noreferrer> 最大子数组问题 。这是使用O（n）中可能的一种动态编程解决方案。 = noreferrer>卡丹算法：

This is a classic problem in optimization, and it's called the maximum subarray problem. Here's one possible dynamic programming solution in O(n), using Kadane's algorithm:

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)

以上将单次返回具有最大和，子序列的起始索引和终止索引的元组。例如，使用问题中的样本输入：

The above will return in a single pass a tuple with the maximum sum, the starting index and the end index of the subsequence. For example, using the sample input in the question:

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]

请注意，维基百科页面上显示的实现（看起来很像您想要的解决方案）仅给出最大和，但是与我的解决方案不同，它们没有告诉您如何在数组中查找子序列索引。

Notice that the implementations shown in the wikipedia page (which look a lot like the solution you were aiming for) only give the maximum sum, but unlike my solution they don't tell you how to find the subsequence indexes in the array.

这篇关于查找具有最大和的连续子集的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！