I have an m x n matrix which is sparse with N non-zero entries. A modified version of Kadane's 2-d algorithm can find the maximum sum subrectangle in O(m N log n) time, which beats traditional Kadane's 2-d algorithm of O(m^2 n) for sufficiently sparse matrices. The sparse matrix algorithm, which is also O(m^2 n) time for dense matrices, matching Kadane's algorithm, can be found here https://stackoverflow.com/questions/17558028/maximum-sum-subrectangle-in-a-sparse-matrix .Now I want to know if the optimal solution can be updated quickly if one entry in the matrix is changed. By "quickly" I mean something like O(m log n) time or better. It's possible that perhaps the matrix does not have to be sparse to work out a solution, however a solution when N = O(min(m,n)) would be ok. Preprocessing is also ok as long as the amortized cost of preprocessing time per element changed matches or beats something like O(m log n) time for m changes.
-
$\begingroup$ To make the question self-contained and help us help you, would you be able to provide a description or summary of Kadane's 2-d algorithm or a link to a description of it? $\endgroup$– D.W. ♦Commented Jan 21, 2014 at 18:01
-
$\begingroup$ @D.W. thanks, link to the existing algorithm is now given. $\endgroup$– user2566092Commented Jan 21, 2014 at 19:54
-
$\begingroup$ Thanks, that's interesting reading. It still doesn't seem to offer a description of Kadane's algorithm, though. Do you have a reference for Kadane's algorithm? Perhaps you might want to add the main ideas of Kadane's algorithm to the question to make your question self-contained. $\endgroup$– D.W. ♦Commented Jan 21, 2014 at 20:21
1 Answer
Yes, absolutely. There is a straightforward way to do what you want, if you work through the details of the algorithm given at the link in your question. The trick is to use persistent data structures, to avoid re-computing data multiple times.
The algorithm given at your link builds a one-dimensional array A[] for each i,j (where $1\le i \le j \le m$), where A[k] = sum{B[i..j,k]}. So, let's keep a copy of each of those arrays. That can be done by using a persistent data structure for the array, say, a persistent balanced binary tree. In this way, the output of the algorithm shown there is $m(m-1)/2$ 1-D arrays, one for each i,j.
Now let's say that the entry B[i*,k] gets modified in the matrix B. Obviously, this affects the entry A[k] in each of the arrays for i,j, where i <= i* <= j. That's at most $O(m^2)$ of the 1-D arrays. And, we can go update that one entry of those arrays in $O(m^2)$ time. In fact, for a sparse matrix, the running time is even less: it is something like the square of the number of non-zero entries in the k-th column of the matrix B.
