Computer Science Canada Array+dynamic programming |
| Author: | fabiocaravieri [ Sun May 08, 2011 2:55 pm ] |
| Post subject: | 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. |
|
| Author: | Tony [ Mon May 09, 2011 10:37 am ] |
| Post subject: | RE:Array+dynamic programming |
So what's the question? |
|
| Author: | fabiocaravieri [ Mon May 09, 2011 11:01 am ] |
| Post subject: | Re: RE:Array+dynamic programming |
Tony @ Mon May 09, 2011 10:37 am wrote: 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 |
|
| Author: | Tony [ Mon May 09, 2011 11:18 am ] |
| Post subject: | 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. |
|
| Author: | A.J [ Mon May 09, 2011 12:07 pm ] |
| Post subject: | 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). |
|