Page 1 of 1
Classic matrix problem
Posted: Wed Dec 20, 2006 2:43 pm
by forest
Find a rectanglular submatrix of a matrix with maximum sum of its elements. What is an optimal solution for this.
Posted: Wed Dec 20, 2006 10:11 pm
by Jan
I think the best solution is O(n^3).
Posted: Fri Dec 22, 2006 10:27 am
by forest
Is there a faster one ?
Posted: Fri Dec 22, 2006 4:46 pm
by Moheeb
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.
Posted: Mon Dec 25, 2006 8:02 am
by SRX
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!
Posted: Sun Dec 31, 2006 6:27 am
by Cosmin.ro
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.