这是优化过程中的经典问题，称为 最大子数组问题 。这是使用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.