Реализация алгоритма максимального прямоугольника

Я пытаюсь реализовать алгоритм максимального прямоугольника от доктора Доббса (листинг 4) с помощью Python. Он работает в основном, но один конкретный случай дает неправильные результаты, и я не могу понять, почему.

Вот мой исходный код:

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 

И вот результат:

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

Как вы можете видеть, первый пункт неверен, но я не могу понять, где и почему он идет не так. Изменение arr дает правильные результаты.

Изменить: я заметил, что изменил значения массива по сравнению со статьей. Это изменяет сравнение в update_cache. 0 = clear и 1 = зарезервировано. Я ищу результат (точка (X = 0, Y = 1), точка (X = 1, Y = 2)).

Последний стек.append должен быть:

 stack.append((y0, w0))