可能重复:
在实数列表中查找最大间隔总和.
我今天在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中实现的算法.
提前致谢