Maximum two-dimensional subset-sum

Question

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.

Answer 1

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.

Answer 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.