CODEWITHSUNDEEP
algorithmsubmatrix
Meir
Meir

Reputation: 12755

Finding a submatrix with the maximum possible sum in O(n^2)

I'm trying to write a program in Java that when given an MxN matrix it will find the (contiguous) submatrix with the biggest sum of numbers. The program then needs to return the top left corner coordinates of the submatrix and the bottom right corner coordinates. The matrix can include negative numbers and both the matrix and submatrix don't need to be square.

I saw that this was discussed here: Getting the submatrix with maximum sum? and the solution there seems to be O(n^3). A friend of mine said that they had once managed to solve this problem in O(n^2). Also suggested here. Is that possible?

Is there any available code out there that solves this problem in the most efficient way?

Upvotes: 3

Views: 4482

Answers (2)

AviD
AviD

Reputation: 302

(S)He's a friend of yours.. so just ask him/her, and do share with us too :)

Upvotes: 4

IVlad
IVlad

Reputation: 43477

You (most likely) can't solve your problem in O(n^2), at least no such algorithm is known. The optimal solution has sub-cubic complexity, but it's very hard to implement and probably slower in practice. You can read a paper about it here.

The usual algorithm used is the O(n^3) one referenced in the question you found.

Upvotes: 7

Related Questions