# Finding a sub rectangle with maximum sum

Given a $n \times n$ matrix filled with positive or negative numbers, find a sub rectangle with maximum sum and output the sum.

There's a well-known algorithm which runs in $O(n^3)$, but can the complexity be improved any further?

In Tadao Takaoka, Efficient Algorithms for the Maximum Subarray Problem by Distance Matrix Multiplication, In Electronic Notes in Theoretical Computer Science, Volume 61, 2002, Pages 191-200 you can find a simplified algorithm (the original is by Tamaki and Tokuyama) that runs in sub-cubic time for $m \times n$ arrays:
$$O ( m^2 n (\log \log m / \log m)^{1/2})$$