title: Largest sum contiguous subarray (Interview Question)
body: <blockquote>
    <p><strong>Possible Duplicate:</strong><br>
    <a href="https://stackoverflow.com/questions/5331040/find-the-maximum-interval-sum-in-a-list-of-real-numbers">Find the maximum interval sum in a list of real numbers.</a>  </p>
  </blockquote>
  
  
  
  <p>I was asked the following question today at Adobe interview for the position of software engineer.</p>
  
  <p><strong>Problem</strong>  Given a array <code>arr[1..n]</code> 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.</p>
  
  <p><strong>Example</strong>  </p>
  
  <p>Given array <code>arr[1..6] = [ 12, 14, 0, -4, 61, -39 ]</code></p>
  
  <p><strong>Answer</strong> </p>
  
  <p>83 constructed with <code>[ 12, 14, 0, -4, 61 ]</code>.</p>
  
  <p>I could come up with a solution running in <code>O(n logn)</code> but I don't think it was very efficient. The interviewer asked to me to write an <code>O(n)</code> algorithm. I couldn't come up with it.</p>
  
  <p>Any idea about how to write an <code>O(n)</code> solution for this problem?
  Algorithm to be implemented either in C/C++/Java.</p>
  
  <p>Thanks in advance</p>