如何在数组中找到最大连续SUM(包含正数和负数)？

Question

我想编写一个函数ContigSum(i,j),计算连续元素的和a[i]通过a[j],其中i<=j和a[]包含正数和负数.

你能告诉我一个时间有效的解决方案,找到阵列中最大化的连续SUM吗？

Answer 1

关于这个主题的维基百科条目中有很好的解释.我发现他们为Kandane算法提供的Python代码(即可执行的伪代码)是一个小宝石:

def max_subarray(A):
    max_so_far = max_ending_here = 0
    for x in A:
        max_ending_here = max(0, max_ending_here + x)
        max_so_far = max(max_so_far, max_ending_here)
    return max_so_far