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

Postby jones » Mon May 27, 2013 8:08 am

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

Postby setrofim » Mon May 27, 2013 9:20 am

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

Postby jones » Mon May 27, 2013 4:28 pm

-
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

Postby Crimson King » Mon May 27, 2013 6:06 pm

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.
User avatar
Crimson King
 
Posts: 132
Joined: Fri Mar 08, 2013 2:42 pm
Location: Buenos Aires, Argentina


Return to General Coding Help

Who is online

Users browsing this forum: Bookwormnathan and 7 guests