最大的一笔连续的子阵列(面试问题) [英] Largest sum contiguous subarray (Interview Question)
问题描述
可能重复:
<一href="http://stackoverflow.com/questions/5331040/find-the-maximum-interval-sum-in-a-list-of-real-numbers">Find最大时间间隔总和在实数的一个列表
我提出以下问题,在今天接受采访的Adobe软件工程师的位置。
I was asked the following question today at Adobe interview for the position of software engineer.
问题给定一个数组改编[1..1]
整数。写一个算法来找到具有最大总和的阵列内相邻的子阵列的总和。返回0,如果所有的数字都是负面的。
Problem Given 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.
示例
由于阵改编[1..6] = [12,14,0,-4,61,-39]
答案
83 [12,14,0,-4,61]
。
我可以在解决方案运行拿出为O(n LOGN)
,但我不认为这是非常有效的。问我的面试官写了 O(N)
算法。我不能来了吧。
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)
针对此问题的解决方案,任何想法?
算法采用C语言实现/ C ++ / Java的。
Any idea about how to write an O(n)
solution for this problem?
Algorithm to be implemented either in C/C++/Java.
在此先感谢
推荐答案
您可以使用 Kadane的这些运行在O算法 (N)。
下面是该算法(从这里 无耻地复制)
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
这篇关于最大的一笔连续的子阵列(面试问题)的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!