可能的重复：
找出实数列表中的最大间隔总和。 https://stackoverflow.com/questions/5331040/find-the-maximum-interval-sum-in-a-list-of-real-numbers
今天在 Adobe 面试软件工程师职位时，我被问到了以下问题。
Problem给定一个数组arr[1..n]整数。编写一个算法来查找数组中具有最大总和的连续子数组的总和。如果所有数字均为负数，则返回 0。
Example
给定数组arr[1..6] = [ 12, 14, 0, -4, 61, -39 ]
Answer
83 建造用[ 12, 14, 0, -4, 61 ].
我可以想出一个运行的解决方案O(n logn)但我认为这不是很有效率。面试官要求我写一篇O(n)算法。我想不出来。
关于如何编写的任何想法O(n)这个问题的解决方案？
用 C/C++/Java 实现的算法。
提前致谢
您可以使用卡丹算法 http://en.wikipedia.org/wiki/Maximum_subarray_problem其运行时间为 O(n)。
这是算法（无耻地复制自here http://geeksforgeeks.org/?p=576)
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
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
