Classic matrix problem

Let's talk about algorithms!

Moderator: Board moderators

Post Reply
forest
New poster
Posts: 11
Joined: Sat Sep 02, 2006 5:13 pm
Contact:

Classic matrix problem

Post by forest »

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

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan »

I think the best solution is O(n^3).
Ami ekhono shopno dekhi...
HomePage

forest
New poster
Posts: 11
Joined: Sat Sep 02, 2006 5:13 pm
Contact:

Post by forest »

Is there a faster one ?

Moheeb
New poster
Posts: 21
Joined: Fri May 05, 2006 9:08 am
Location: Dhaka ,Bangladesh

Post 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.

SRX
Learning poster
Posts: 63
Joined: Sat May 14, 2005 8:13 am
Location: Taiwan

Post 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!
studying @ ntu csie

Cosmin.ro
Learning poster
Posts: 95
Joined: Thu Aug 21, 2003 12:02 am

Post 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.

Post Reply

Return to “Algorithms”