最大和的连续子阵列(访谈问题)

Question

可能重复:
在实数列表中查找最大间隔总和.

我今天在Adobe面试中被问到以下问题,担任软件工程师的职位.

问题 给定一组arr[1..n]整数.编写一个算法来查找数组中具有最大总和的连续子阵列的总和.如果所有数字都是负数,则返回0.

例

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

回答

83用[ 12, 14, 0, -4, 61 ].构造.

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

有关如何O(n)为此问题编写解决方案的任何想法？要在C/C++/Java中实现的算法.

提前致谢

Answer 1

您可以使用在O(n)中运行的Kadane算法.

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

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