Take the 2-minute tour ×

I'm given a task to write an algorithm to compute the maximum two dimensional subset, of a matrix of integers. - However I'm not interested in help for such an algorithm, I'm more interested in knowing the complexity for the best worse-case that can possibly solve this.

Our current algorithm is like O(n^3).

I've been considering, something alike divide and conquer, by splitting the matrix into a number of sub-matrices, simply by adding up the elements within the matrices; and thereby limiting the number of matrices one have to consider in order to find an approximate solution.

share|improve this question
That would be the matrix itself, right? ;) –  John Jan 25 '11 at 18:44
What? - Not sure I get what your saying, really wouldn't it depend on wether theres negatives numbers in the matrix? –  Skeen Jan 25 '11 at 18:45
Ahh good point. You did say integers not non-negative integers. ;) So you're looking for a sub-rectangle of numbers within your matrix such that the sum of the numbers in that rectangle is the maximum of that of all possible rectangles? –  John Jan 25 '11 at 18:48
Yes indeed, or morelikely I'm looking for the complexity of the best algorithm for it –  Skeen Jan 25 '11 at 18:51

2 Answers 2

Worst case (exhaustive search) is definitely no worse than O(n^3). There are several descriptions of this on the web.

Best case can be far better: O(1). If all of the elements are non-negative, then the answer is the matrix itself. If the elements are non-positive, the answer is the element that has its value closest to zero.

Likewise if there are entire rows/columns on the edges of your matrix that are nothing but non-positive integers, you can chop these off in your search.

share|improve this answer
up vote 0 down vote accepted

I've figured that there isn't a better way to do it. - At least not known to man yet. And I'm going to stick with the solution I got, mainly because its simple.

share|improve this answer

Your Answer


