title: maximum sum subrectangle in a sparse matrix
body: <p>Finding the maximum sum subrectangle in an <code>NxN</code> matrix can be done in <code>O(n^3)</code> time using 2-d kadane's algorithm, as pointed out in other posts.  However, if the matrix is sparse, specifically <code>O(n)</code> non-zero entries, can the <code>O(n^3)</code> time be beaten?  </p>
  
  <p>If it helps, for the current application I'm interested in, it would suffice to have a solution that assumes at most one non-zero value in each row and in each column of the matrix.  However, in my future applications this assumption might not be appropriate (just sparsity will hold), and anyway my mathematical intuition is that there may be good solution(s) that simply exploit sparsity and don't further exploit the fact that the matrix is a product of a diagonal and a permutation matrix.</p>