Finding a sub rectangle with maximum sum
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}) $$

From the paper: ... Bentley's algorithm is cubic and the Tamaki-Tokuyama algorithm is sub-cubic for a nearly  square array. Their algorithm is heavily recursive and complicated. We simplify the latter algorithm, and achieve sub-cubic time for any rectangular array ...

They also give a more practical algorithm whose expected time is close to quadratic for a wide range of random data.