All geek questions in one place

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

I am trying to write a program in Java which, when specifying the matrix MxN, will find the (adjacent) submatrix with the largest sum of numbers. Then the program needs to return the upper left corner coordinates of the submatrix and the lower right corner coordinates. The matrix can contain negative numbers, and both the matrix and the submatrix must not be square.

I saw this discussed here: Getting the submatrix with the maximum amount? , and the solution there seems to be O (n ^ 3). A friend of mine said that they were able to solve this problem in O (n ^ 2). Also offered here. Is it possible?

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

+3
source share
2 answers

You (most likely) cannot solve your problem O(n^2); at least, such an algorithm is not known. The optimal solution has subcubic complexity, but it is very difficult to implement and, probably, slower in practice. You can read an article about it here .

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

+7
source

(S) He is your friend ... so just ask him / her and share with us too :)

+4
source

Source: https://habr.com/ru/post/1751715/

More articles:


All Articles