-----------------------------------

fabiocaravieri

Sun May 08, 2011 2:55 pm


Array+dynamic programming

-----------------------------------

I work for a school, could someone help me ....
Suppose you are given an mX n bitmap, represented by an array M[1..m, 1.. n] whose entries are all 0 or 1. A solid block is a subarray of the form M[i .. i', j .. j'] in which every bit is equal to 1.
Describe and analyze an efficient algorithm to find a solid block in M with maximum area.


-----------------------------------

Tony

Mon May 09, 2011 10:37 am


RE:Array+dynamic programming

-----------------------------------

So what's the question?


-----------------------------------

fabiocaravieri

Mon May 09, 2011 11:01 am


Re: RE:Array+dynamic programming

-----------------------------------

So what's the question?

I'm having difficulty producing a sub array with a larger amount of 1. If you can give any tips, I appreciate


-----------------------------------

Tony

Mon May 09, 2011 11:18 am


RE:Array+dynamic programming

-----------------------------------

So your base case is a 1x1 subarray with a total of one bit. That should be fairly easy to recognize. Start with that.


-----------------------------------

A.J

Mon May 09, 2011 12:07 pm


RE:Array+dynamic programming

-----------------------------------

@fabiocaravieri - Are you getting these questions from an Algorithms course? Or are you asking us questions you encountered on some book/website?

If it is the former, I understand that you might need help with the concept of DP. However, if it is the latter, I HIGHLY recommend you attempting these problems on your own prior to asking for help, as when it comes to algorithmic programming, experience plays a huge part (especially with DP problems).