Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

This question is from an ongoing contest which ends in 4 days. It is this problem from the October Challenge.

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.

share|improve this question
    
So the submatrix can be whatever (rectangular) shape you want? So for example, if all entries except one were negative, and the remaining one were "30", the answer would be 30? It seems like a fairly complicated task :) –  rschwieb Oct 2 '12 at 20:33
    
@rschwieb:no actually the requirement is to find the submatrix itself not the sum .ie you have the column and the row extent and the rows and columns included in the submatrix as the answer.It is not required to find the max sum itself –  user43255 Oct 3 '12 at 18:19
    
In the case I described, the submatrix is $[30]$ itself. If that is not the case then I still don't know what you mean by submatrix. –  rschwieb Oct 3 '12 at 18:35
    
@rschwieb:I mean i just need to know the column number say C and row number R of [30] and the row extent=1 and column extent=1 (row extent is how much the row extends from the origin) Origin can be given as the left top most indices of the sub matrix –  user43255 Oct 3 '12 at 23:36

1 Answer 1

Kadane's Algorithm.

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:

kadane($x_1,\ldots,x_n$):

$\hspace{10pt}$$m \leftarrow -\infty$, $\hspace{10pt}$$a \leftarrow 0$, $\hspace{10pt}$$b \leftarrow 0$,

$\hspace{10pt}$$c_m\leftarrow 0$, $\hspace{10pt}$$c_a\leftarrow 1$

$\hspace{10pt}$for $c_{\,b}=1$ to $n$ do

$\hspace{30pt}$$c_m \leftarrow c_m \!+\, x_b$

$\hspace{30pt}$if $c_m>m$ then

$\hspace{50pt}$$m \leftarrow c_m$, $\hspace{10pt}$$a\leftarrow c_a$, $\hspace{10pt}$$b\leftarrow c_{\,b}$

$\hspace{30pt}$if $c_m<0$ then

$\hspace{50pt}$$c_m \leftarrow 0$, $\hspace{10pt}$$c_a\leftarrow c_{\,b}+1$

$\hspace{10pt}$return $m,a,b$

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.

share|improve this answer
    
"Determining the maximum submatrix in this context means finding the maximum contiguous subsequence..." But the question explicitly states that the submatrix need not be contiguous. –  Gerry Myerson Oct 7 '12 at 23:14
    
Yes, "in this context" refers to the context of Kadane's algorithm, as opposed to that of the question - apologies for the lack of clarity. My later suggestion about permutations is what makes me believe an adaption of this will be useful. –  Alexander Gruber Oct 7 '12 at 23:18

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.