Max square sub-matrix problem

This is the place for queries that don't fit in any of the other categories.

Max square sub-matrix problem

Hey guys. I have a problem I need to solve with dynamic programming for the university. As I'm pretty new to Python I'm asking you for help.

The problem:
Given a mxn matrix of positive and negative integers, write code to find the square sub-matrix with the largest possible sum.

The problem is similar to this one, but it needs to be a square submatrix:

http://www.delbertbao.net/2012/01/25/ma ... em-matrix/

So any code or pseudocode would be very helpful.

Thanks
jones

Posts: 2
Joined: Mon May 27, 2013 8:00 am

Re: Max square sub-matrix problem

We will not do your homework for you. However, we may help you come up the the solution yourself. How far did you get on your own? Which part of this is giving your trouble? Post some code (using [code] tags please).
setrofim

Posts: 288
Joined: Mon Mar 04, 2013 7:52 pm

Re: Max square sub-matrix problem

-
Last edited by jones on Thu May 30, 2013 3:30 pm, edited 1 time in total.
jones

Posts: 2
Joined: Mon May 27, 2013 8:00 am

Re: Max square sub-matrix problem

jones wrote:I have the idea written with words but I really don't know how to put it in code.

I'll show you on a simple example how it should be solved (it is similar to Kadane's 2D algorithm), I just need to put it into code but I don't have the idea how to (time complexity should be 0(n^3)).
...

Hey jones, you should definitely check out some tutorials about python programming (there's a couple in the tutorial section) . It wouldn't help you at all if we wrote the code that solved this and as setrofim told you "We will not do your homework for you".

The users here are really helpful when they see that you put some effort to code the solution (doesn't matter if it's ugly). So, try your best to translate what your idea is to python code.

Crimson King

Posts: 153
Joined: Fri Mar 08, 2013 2:42 pm
Location: Buenos Aires, Argentina