title: Kadane Algorithm Negative Numbers
body: <pre><code>int array[] = {-1, 4, -2, 5, -5, 2, -20, 6};
  </code></pre>
  
  <p>If I had that array, my Kadane algorithm implementation to find the maximum subarray works:</p>
  
  <pre><code>  int max_so_far = INT_MIN;
    int max_ending_here = 0;
    for (int i = 0; i &lt; size; i++) {
      max_ending_here = max(max_ending_here + array[i], 0);
      max_so_far = max(max_ending_here, max_so_far);
    }
  
    printf("%d\n", max_so_far);
  </code></pre>
  
  <p>However, if I have an array of all negatives:</p>
  
  <pre><code>int array[]= {-10, -10, -10};
  </code></pre>
  
  <p>It won't work, it should return -10, but I get 0.</p>
  
  <p>How can I make it work for negative numbers too?</p>
  
  <p>Thank you!</p>