7
$\begingroup$

Given a $n\times m$ matrix $A$ of integers, find a sub-matrix whose sum is maximal. If there is one row only or one column only, then this is equivalent to finding a maximum sub-array.

The 1D version can be solved in linear time by dynamic programming. The 2D version can be solved in $\cal O(n^3)$ by looping over all pairs of columns and using the 1D algorithm on the array whose length is the number of rows in the matrix where each position $r$ holds the sum of the elements at row $r$ between the two columns.

If the matrix is given by:

\begin{pmatrix} 1 & -2 & 0 & -1 \\ 5 & 43 & 31 & 78 \\ -45 & -12 & 19 & 9 \end{pmatrix}

Then for the pair of columns $(0,2)$, the max sub-matrix sum can be found by using the 1D algorithm on the array (top to bottom):

\begin{pmatrix} 1-2+0 & = & -1 \\ 5+43+31 & = & 79\\ -45-12+19 & = & -38 \end{pmatrix} Does anybody know of a $\cal O(n^2)$ algorithm for solving this problem?

$\endgroup$
  • $\begingroup$ Check out this video explaining this question. youtu.be/yCQN096CwWM $\endgroup$ – user33438 May 8 '15 at 1:24
2
$\begingroup$

I found this: Sung Eun Bae, Sequential and Parallel Algorithms for the Generalized Maximum Subarray Problem. Read pages 18-30, where it says that there are just cubic $O(nm^2)$ and sub-cubic algorithms for this problem (in general case), for example Tadao Takaoka's $O\left(n^3 \sqrt{\frac{\log\log n }{\log n }}\right)$ algorithm.

I've also found a forum comment saying that this problem can be solved in $O(N^2\log N )$ for matrices with N non-zero elements using "funny" segment tree (you can ask commentator about details).

$\endgroup$
  • $\begingroup$ The only thing that I hate about this site is that it's written in Russian (I use it a lot though). $\endgroup$ – saadtaame Jun 3 '14 at 15:40
  • $\begingroup$ @saadtaame I think it's written in PHP. And you can use translators to understand texts written in Russian. But I advise you to not say those words "I hate", "to don't insult feelings of believers" (rus. proverb). Some of us (generally, those who know foreign languages) are very proud of our boundless language (so do I). А вот это перевести нечерезче. $\endgroup$ – Ralor Jun 3 '14 at 20:52
  • $\begingroup$ Didn't mean to hurt your feelings buddy, sorry. Yes I use translators (I said that I use the site a lot). Well, you can do us a great favor by translating the site to English. $\endgroup$ – saadtaame Jun 3 '14 at 21:11

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.