Given:A Matrix (Not necessarily square) filled with negative and positive integers.What will be good way of finding the sub matrix with the largest sum and this sub matrix may not be contiguous such that you can select columns 1 and 3 and rows 1 and 3 and leave out column 2 and row 2? Any hints/suggestions/tricks will help a lot.
- Anybody can ask a question
- Anybody can answer
- The best answers are voted up and rise to the top
Before we get into bigger matrices, let's just consider $1\times n$ matrices - that is, integer sequences of length $n$. Determining the maximum submatrix in this context means finding the maximum contiguous subsequence, and for that we have Kadane's algorithm, which runs for the low low price of $O(n)$. It goes like this:
So, given an integer sequence $x_1,\ldots, x_n$, kadane will return the maximum sum $m$ and the endpoints on the interval from which it is attained: $a$ to $b$.
Adapting this to your problem.
To solve your problem, you will first have to adapt Kadane's algorithm to the $m\times n$ case. This isn't too hard; it's just a "double Kadane," going in two directions, ultimately coming out at $O(n^3)$. Since I now see this problem is for a contest, I won't finish it explicitly for you. However, my thought/suggestion is to see if you can use the $2$-dimensional Kadane in conjunction with permutations of rows and columns, then figure out the most efficient way to track the action on the sum.