3
$\begingroup$

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?

$\endgroup$
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.