Given a representation of a 2D surface (as nested list of 1’s and 0’s), find the area of the largest rectangle that is present on the
surface. A rectangle in this case is a m ×n portion of the surface such that all positions within this portion contain a 1. In other
words, this means that the rectangle we are finding has to be a solid rectangle that is unbroken and continuous. The area of this
rectangle then, is the number of 1’s that it contains (equal to m × n). This problem by itself might be harder than it looks, so
lets first look at how we might solve a subset of the problem, as detailed in the paragraph below.
Instead of trying to figure out what the area of the largest rectangle in the whole matrix is, we first figure out what the
area of the largest rectangle is for a given point on the matrix. This means that for a given x, y coordinate on the matrix, we
figure out the area of the largest rectangle whose top left corner starts at that point.
Take for example this nested list: [ [1, 0, 1, 0, 0],
[1, 0, 1, 1, 1], ( to see red , green ) look at screenshot .
[1, 1, 1, 1, 1],
[ 1 , 0, 0, 1, 0]]
If we look at the position (0 indexing), we see that there are two potential rectangles that can be formed. One length-wise
which produces a rectangle of area 5 (red), and one height-wise which produces a rectangle of area 2 (green). We want our
function for this sub-problem to return the largest of these rectangles, and so in this case it would return 5. Keep in mind that
rectangles need not be only one row or column, they could consist of multiple rows and columns, like the one you see at position
with an area of 6 (blue), which happens to be the largest rectangle in the whole matrix.
Admittedly, this problem is harder than those seen in the previous labs, so here are some guiding points to get you started. You
must complete the tasks below in order, as each task builds on the previous one, and for each function you need to make use of
the previous one as a helper.
1. First, make sure the function longest_chain
2. Once you have completed the helper function, you can start implementing largest at position, which makes use of
longest chain. The main idea here is to loop through every row at the specified column and check how many consecutive
1’s there are on each row (beginning at that column). We suggest drawing this out on paper and coming up with a few test
cases yourself to try to visualise it. It really is quite interesting. Note: visualisation is an important tactic programmers
use to help problem solve, this is a chance for you to practice this skill!
3. While looping through the rows, you’ll find that you need about three variables, one to keep track of the maximum sized
rectangle you’ve seen so far, and another to keep track of the number of rows you’ve seen. We’ll leave the third variable for
you to figure out, but it has something to do with the longest chain function you just wrote. It’s important to note that
in order for longest chain to work properly, you’ll need to pass it a list that starts at the position that you are interested
in, so there’s some list slicing to do on each row here. Once you have the loop set up and have all the variables updating
correctly, some simple arithmetic in every loop should be able to get you the rectangle size on each iteration. The idea
here is that for every loop, you need to calculate the largest rectangle that you can form from the part of the matrix you’ve
seen so far. And the largest of these rectangles is the largest rectangle at this position. (This step is the most tricky!)
4. Finally, once largest at position is working correctly, the final function is easy to implement. Implement largest in matrix
by looping through each position in the matrix and calling largest at position. The largest rectangle in the matrix
must be the largest rectangle in all of the positions.
checking (final part)
1. written doctests and ensured that they pass?
2. considered edge cases in your doctests?
3. run it to see if its working