java 最大和连续子数组（面试题）
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/5378273/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Largest sum contiguous subarray (Interview Question)
提问by WebDev
Possible Duplicate:
Find the maximum interval sum in a list of real numbers.
可能的重复：
在实数列表中找到最大间隔和。
I was asked the following question today at Adobe interview for the position of software engineer.
今天在 Adobe 的软件工程师职位面试中，我被问到以下问题。
ProblemGiven a array arr[1..n]of integers. Write an algorithm to find the sum of contiguous subarray within the array which has the largest sum. Return 0 if all the numbers are negative.
问题给定一个arr[1..n]整数数组。写一个算法来找出数组中连续子数组的和，它的和最大。如果所有数字都是负数，则返回 0。
Example
例子
Given array arr[1..6] = [ 12, 14, 0, -4, 61, -39 ]
给定数组 arr[1..6] = [ 12, 14, 0, -4, 61, -39 ]
Answer
回答
83 constructed with [ 12, 14, 0, -4, 61 ].
83 用[ 12, 14, 0, -4, 61 ].
I could come up with a solution running in O(n logn)but I don't think it was very efficient. The interviewer asked to me to write an O(n)algorithm. I couldn't come up with it.
我可以想出一个解决方案，O(n logn)但我认为它不是很有效。面试官让我写一个O(n)算法。我想不出来。
Any idea about how to write an O(n)solution for this problem?
Algorithm to be implemented either in C/C++/Java.
关于如何O(n)为这个问题编写解决方案的任何想法？要在 C/C++/Java 中实现的算法。
Thanks in advance
提前致谢
回答by Prasoon Saurav
You can use Kadane's algorithmwhich runs in O(n).
您可以使用以 O(n) 运行的Kadane 算法。
Here is the algorithm (shamelessly copied from here)
这是算法（从这里无耻地复制）
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
