最大和连续子阵(采访问题)

Question

可能重复： 在实数列表中找到最大间隔和。

今天Adobe面试软件工程师职位时，我被问到以下问题。

问题给出了一个整数数组arr[1..n]。编写一个算法来查找数组中连续子数组的和，该子数组的和最大。如果所有数字为负数，则返回0。

示例

给定阵列arr[1..6] = [ 12, 14, 0, -4, 61, -39 ]

答案

用[ 12, 14, 0, -4, 61 ]构建83份。

我可以想出一个在O(n logn)中运行的解决方案，但我不认为它非常有效。面试官要求我写一个O(n)算法。我想不出来。

对于如何为这个问题编写O(n)解决方案，有什么想法吗？算法将在C/C++/Java中实现。

提前感谢

Answer 1

您可以使用运行在O(n)中的卡达内算法。

下面是算法(无耻地从这里复制)

Initialize:
    max_so_far = 0
    max_ending_here = 0

Loop for each element of the array
  (a) max_ending_here = max_ending_here + a[i]
  (b) if(max_ending_here < 0)
            max_ending_here = 0
  (c) if(max_so_far < max_ending_here)
            max_so_far = max_ending_here
return max_so_far