title: Kadane's algorithm to find subarray with the maximum sum
body: <p>I have the following implementation of <a href="http://en.wikipedia.org/wiki/Maximum_subarray_problem" rel="noreferrer">Kadane's algorithm</a> to solve the problem of the maximum subarray of an array:</p>
  
  <pre><code>public static decimal FindBestSubsequence
      (this IEnumerable&lt;decimal&gt; source, out int startIndex, out int endIndex)
  {
      decimal result = decimal.MinValue;
      decimal sum = 0;
      int tempStart = 0;
  
      List&lt;decimal&gt; tempList = new List&lt;decimal&gt;(source);
  
      startIndex = 0;
      endIndex = 0;
  
      for (int index = 0; index &lt; tempList.Count; index++)
      {
          sum += tempList[index];
          if ((sum &gt; result) || 
              (sum == result &amp;&amp; (endIndex - startIndex) &lt; (index - tempStart)))
          {
              result = sum;
              startIndex = tempStart;
              endIndex = index;
          }
          else if (sum &lt; 0)
          {
              sum = 0;
              tempStart = index + 1;
          }
      }
  
      return result;
  }
  </code></pre>
  
  <p>It fails when I use a sequence that starts with a negative number like <code>-1, 2, 3</code> giving a result of <code>4, [0,2]</code> instead of <code>5, [1,2]</code>.</p>
  
  <p>For the life of me that I cannot find where the error is. Maybe its a defect on the algorithm design?</p>
  
  <p>Thanks in advance.</p>