Hello i have been thinking on this question for quite a while, but i can't find the answer. As i have read in many forums it is possible to solve the maximum-subarray-sum problem (usually solved by Kadane's algorithm) using Segment Trees, then obviously the question came by, is it possible to solve the maximum-submatrix-sum problem using Segment Trees? , i think it should be faster than the O(N^3) adapted Kadane's algorithm.
:) just a question trying to learn more
I doubt there is something better than O(N^3).
I can't think of a clever way to use segment trees since after all in the maximum-submatrix-sum problem you don't have any updates. So sum of a subrmatrix can be found in O(1) after preprocessing, so I can't see how segment trees can help.
But who knows, there might be some crazy O(N^2 log^2 N) solution.
Well, probably you meant N^2 log^2 N.
At least you need to read all the matrix:)
Yep, fixed it, of course I meant O(N^2 log^2 N) :D
I did some extensive searching on this topic before and didn't find anything interesting. You can more or less safely assume that no better approach is known in general case, while some improvements can be made for particular cases (like small integers for matrix entries or such); alas, I don't have any links for this.