Classic matrix problem

forest · Post by **forest** » Wed Dec 20, 2006 2:43 pm

Find a rectanglular submatrix of a matrix with maximum sum of its elements. What is an optimal solution for this.

Jan · Post by **Jan** » Wed Dec 20, 2006 10:11 pm

I think the best solution is O(n^3).

forest · Post by **forest** » Fri Dec 22, 2006 10:27 am

Is there a faster one ?

Moheeb · Post by **Moheeb** » Fri Dec 22, 2006 4:46 pm

Jan wrote

I think the best solution is O(n^3).

I don't think so, According to Bently there' exists sightly faster algorithm than this, though
i don't know that.

SRX · Post by **SRX** » Mon Dec 25, 2006 8:02 am

Jan wrote:I think the best solution is O(n^3).

I heard from someone that there exists a solution using
stack , and its running time is O(n^2) .

I can't find out it .

Can someone give me some link about that ?
thanks!

Cosmin.ro · Post by **Cosmin.ro** » Sun Dec 31, 2006 6:27 am

SRX you're talking about a different problem which asks to find the largest rectangle that doesn't contain any cell with it's value 0.

For the maximal sum problem the best algorithm I know about is very complicated. It is better than the O(n^3) but is slower than O(n^3 / log n) so it doesn't really help.