The implementation of the maximum rectangle algorithm

Question

I'm trying to implement Dr. Dobbs's Maximum Rectangle Algorithm (Listing 4) with Python. It works mostly, but one specific case gives the wrong results, and I cannot understand why.

Here is my source code:

from collections import namedtuple

Point = namedtuple('Point', ('X', 'Y'))

#Y      0  1  2      X
arr = [[0, 0, 0, ], #0
       [1, 0, 0, ], #1
       [0, 0, 1, ], #2
       ]

def area(ll, ur):
    if (ll.X < 0) or (ll.Y < 0) or (ur.X < 0) or (ur.Y < 0):
        return 0.
    return ((ur.X - ll.X) + 1) * ((ur.Y - ll.Y) + 1)

def update_cache(a, c, x):
    M = len(a[0])
    N = len(a)
    for y in range(M):
        if a[x][y] == 0:
            c[y] = c[y] + 1
        else:
            c[y] = 0

def mrp(a):
    best_ll = Point(-1, -1)
    best_ur = Point(-1, -1)
    M = len(a[0]) 
    N = len(a)
    c = [0 for x in range(M + 1)]
    stack = []
    for x in range(N-1, -1, -1):

        update_cache(a, c, x)        
        width = 0
        for y in range(M + 1):
            if c[y] > width:
                stack.append((y, width))                
                width = c[y]
            if c[y] < width:
                while True:
                    y0, w0 = stack.pop()
                    if (width * (y - y0)) > area(best_ll, best_ur):
                        best_ll = Point(x, y0)
                        best_ur = Point(x + width - 1, y - 1)
                    width = w0
                    if (c[y] >= width):
                        break
                width = c[y] 
                if width == 0:
                    stack.append((y0, width))
    return best_ll, best_ur

And here is the result:

>>> mrp(arr)
(Point(X=0, Y=0), Point(X=1, Y=2))

As you can see, the first point is incorrect, but I can’t understand where and why it goes wrong. Changing arr gives correct results.

Edit: I noticed that I changed the values ​​of the array compared to the article. This changes the comparison in update_cache. 0 = clear and 1 = reserved. I am looking for the result (point (X = 0, Y = 1), point (X = 1, Y = 2)).

Answer 1

.append :

stack.append((y0, w0))