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.
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.
Example
Given array arr[1..6] = [ 12, 14, 0, -4, 61, -39 ]
Answer
83 constructed with [ 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.
Any idea about how to write an O(n)
solution for this problem?
Algorithm to be implemented either in C/C++/Java.
Thanks in adva开发者_StackOverflow中文版nce
You can use Kadane's algorithm which runs in 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
精彩评论