title: Understanding Kadane's Algorithm for 2-D Array
body: <p>I'm trying to write a program which solves the <a href="http://en.wikipedia.org/wiki/Maximum_subarray_problem" rel="noreferrer">maximum subarray problem</a>. I can understand the intuition behind Kadane's Algorithm on a 1-D array as well as the O(N^4) implementation on a 2-D array. However, I am having some trouble understanding the O(N^3) implementation on a 2-D array. </p>
  
  <p>1) Why do we add up the elements with those from the previous rows within the same column? </p>
  
  <pre><code>for (int i = 1; i &lt;= N; i++) {
    for (int j = 1; j &lt;= M; j++) 
         array[i][j] += array[i-1][j];
  }
  </code></pre>
  
  <p>2) I have no understanding of the second part of the algorithm</p>
  
  <p>Tried looking for an explanation on the web but to no avail. Hope to get some help here!</p>
  
  <p>Thanks in advance!</p>