Largest sum contiguous subarray (Interview Question)

Question

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 advance

Solution

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

Comments

[a'r]

Here's a link to the wikipedia article for reference: en.wikipedia.org/wiki/Maximum_subarray_problem

[rajya vardhan]

What about this array: [ -12, 14, 0, -4, 61, -39 ] Actual result: [ -12, 14, 0, -4, 61] Expected: [14, 0, -4, 61]