最大四角形アルゴリズムの実装

Question

Maximum Rectangle Algorithm from Dr. Dobbs（リスト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 =クリア、1 =予約済み。私は結果（ポイント（X = 0、Y = 1）、ポイント（X = 1、Y = 2））を探しています。

Answer 1

最終stack.appendあるべき：

stack.append((y0, w0))