<p>In <a href="http://www.sciencedirect.com/science/article/pii/S1571066104003135" rel="nofollow noreferrer">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</a> you can find a simplified algorithm (the original is by Tamaki and Tokuyama) that runs in sub-cubic time for $m \times n$ arrays:</p>

<p>$$O ( m^2 n (\log \log m / \log m)^{1/2}) $$</p>

<p>From the paper: <em>... 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 ...</em></p>

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

CC BY-SA 3.0
2017-09-21T08:23:43.857Z
2017-09-21T08:23:43.857Z
Marzio De Biasi
<p>Given a $n \times n$ matrix filled with positive or negative numbers, find a sub rectangle with maximum sum and output the sum.</p>

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

<cc.complexity-theory><ds.algorithms>
Finding a sub rectangle with maximum sum
newbie
# Finding a sub rectangle with maximum sum

(Asked by: username_0 on 2017-09-21)

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?

**Tags:** cc.complexity-theory, ds.algorithms


---

## 1 answers

### Answer by username_1 on 2017-09-21. Score: 4 | Accepted answer

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](http://www.sciencedirect.com/science/article/pii/S1571066104003135) 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.


---

