Problem:
Largest Rectangle Given a matrix ( H × W ) which contains only 1 and 0, find the area of the largest rectangle which only contains 0s. Input  H  W  c 1,1  c 1,2 ... c 1,W  c 2,1  c 2,2 ... c 2,W : c H,1  c H,2 ... c H,W  In the first line, two integers H and W separated by a space character are given. In the following H lines, c i , j , elements of the H × W matrix, are given. Output Print the area (the number of 0s) of the largest rectangle. Constraints  1 ≤ H , W ≤ 1,400  Sample Input 4 5
0 0 1 0 0
1 0 0 0 0
0 0 0 1 0
0 0 0 1 0 Sample Output 6

Solution (Python):



import sys,bisect
sys.setrecursionlimit(15000)
h,w = map(int,sys.stdin.readline().split())
buffer = [None for _ in range(h)]
T = [[0]*(w+1) for _ in range(h)]

for r in range(h):
  buffer[r] = list(map(int,sys.stdin.readline().split()))

for col in range(w):
  for r in range(h):
    if buffer[r][col] == 1:
      T[r][col] = 0
    elif r == 0:
      T[0][col] = 1
    else:
      T[r][col] = T[r-1][col]+1
m = 0

for buffer in T:
  stack = []
  for i in range(w+1):
    rect = {"h":buffer[i],"p":i}
    if not stack:
      stack.append(rect)
    else:
      if stack[-1]["h"] < buffer[i]:
        stack.append(rect)
      elif stack[-1]["h"] > buffer[i]:
        while stack and stack[-1]["h"] >= buffer[i]:
          pre = stack.pop()
          m = max(m,pre["h"]*(i-pre["p"]))
          rect["p"] = pre["p"]
        stack.append(rect)
print(m)

Solution (Python):
h,w=map(int,input().split())
C=[list(map(int,input().split())) for _ in range(h)]
DP=[[0 for _ in range(w)] for _ in range(h)]

for i in range(w):
    if C[0][i]==0:DP[0][i]=1
    else:DP[0][i]=0

for i in range(1,h):
    for j in range(w):
        if C[i][j]==0:DP[i][j]=DP[i-1][j]+1
        else:DP[i][j]=0

cost=0
for i in range(h):
    stack=[]
    for j in range(w):
        if len(stack)==0:
            stack.append((DP[i][j],j))
        elif DP[i][j]>stack[-1][0]:
            stack.append((DP[i][j],j))
        elif DP[i][j]<stack[-1][0]:
            add=0
            while DP[i][j]<stack[-1][0]:
                rect,pos=stack.pop()
                cost=max(cost,(j-pos)*rect)
                add=pos
                if len(stack)==0:break
            stack.append((DP[i][j],add))

    if len(stack)!=0:
        while len(stack)!=0:
            rect,pos=stack.pop()
            cost=max(cost,(w-pos)*rect)

print(cost)

Solution (Python):


from collections import deque

iim = lambda: map(int, input().rstrip().split())

def calc(dp):
    ans = 0
    dq = deque([[0, 0]])
    
    for i, hi in enumerate(dp):
        j = i
        while dq[-1][1] > hi:
            j, h1 = dq.pop()
            ans = max(ans, (i - j) * h1)

        if dq[-1][1] < hi:
            dq.append([j, hi])

    i = len(dp)
    for j, hi in dq:
        ans = max(ans, (i - j) * hi)
    
    return ans

def resolve():
    H, W = iim()

    dp = [0] * W
    dp0 = dp[:]
    ans = 0
    for i in range(H):
        C = list(iim())

        for i, ci in enumerate(C):
            dp[i] = 0 if ci else dp0[i] + 1

        ans = max(ans, calc(dp))
        dp, dp0 = dp0, dp

    print(ans)

if __name__ == "__main__":
    resolve()

Solution (Python):
def calc_largest_rect_in_hist(heights):
    heights.append(0)
    stack = []
    left = [0] * len(heights)
    ans = 0
    for i, height in enumerate(heights):
        while stack and heights[stack[-1]] >= height:
            idx = stack.pop()
            ans = max(ans, (i - left[idx] - 1) * heights[idx])
        left[i] = stack[-1] if stack else -1
        stack.append(i)
    heights.pop()
    return ans


def aoj_hist():
    
    input()
    print(calc_largest_rect_in_hist([int(x) for x in input().split()]))


def aoj_rect():
    
    H, W = map(int, input().split())
    board = [[int(x) for x in input().split()] for _ in range(H)]
    dp = [0] * W
    ret = 0
    for r in range(H):
        for c in range(W):
            dp[c] = dp[c] + 1 if board[r][c] == 0 else 0
        ret = max(ret, calc_largest_rect_in_hist(dp))
    print(ret)


if __name__ == "__main__":
    
    aoj_rect()

Solution (Python):



class Rectangle:
    def __init__(self, height, position):
        self.height = height
        self.position = position

def getLargestRectangleRow(size, bufTmp):
    S = []
    maxv = 0
    
    bufTmp.append(0)
    for i in range(size + 1):
        rect = Rectangle(bufTmp[i], i)
        
        if len(S) == 0:
            S.append(rect)
        else:
            if S[-1].height < rect.height:
                S.append(rect)
            elif S[-1].height > rect.height:
                target = i
                while len(S) >= 1 and S[-1].height >= rect.height:
                    pre = S.pop()
                    area = pre.height * (i-pre.position)
                    maxv = max(maxv, area)
                    target = pre.position
                rect.position = target
                S.append(rect)
    return maxv


def getLargestRectangle():
    for j in range(W):
        for i in range(H):
            if buf[i][j]:
                T[i][j] = 0
            else:
                if i > 0:
                    T[i][j] = T[i-1][j] + 1
                else:
                    T[i][j] = 1
    maxv = 0
    for i in range(H):
        maxv = max(maxv, getLargestRectangleRow(W, T[i]))

    return maxv


nums=list(map(int,input().split()))
H = nums[0]
W = nums[1]
buf = [[0 for i in range(W)] for j in range(H)]
T = [[0 for i in range(W)] for j in range(H)]
for i in range(H):
    nums=list(map(int,input().split()))
    for j in range(W):
        buf[i][j] = nums[j]

print(getLargestRectangle())

Solution (Python):



from itertools import product, chain


H, W = list(map(int, input().split()))
C = []
for i in range(H):
    C.append(list(map(int, input().split())))




T = []
pre_tmp = [0] * W
for c in C:
    tmp = []
    for cc, pre in zip(c, pre_tmp):
        if cc == 1:
            tmp.append(0)
        else:
            tmp.append(pre + 1)
    T.append(tmp)
    pre_tmp = tmp.copy()


def get_largest_rectangle(hist: list):
    '''
    ヒストグラムが渡されたときに、その中の最大の長方形を返す
    '''
    hist = hist.copy()
    hist.append(0)
    ret = 0
    stack = []
    for i, v in enumerate(hist):
        
        if len(stack) == 0:
            stack.append((i, v))
        elif stack[-1][1] < v:
            stack.append((i, v))
        elif stack[-1][1] > v:
            while stack and stack[-1][1] > v:
                
                
                i_left, h = stack.pop()
                ret = max(ret, (i - i_left) * h)
            stack.append((i_left, v))
    return ret



ans = 0
for t in T:
    ans = max(ans, get_largest_rectangle(t))
print(ans)

Solution (Python):
h,w=map(int,input().split())
C=[list(map(int,input().split())) for i in range(h)]

def Largest_Rectangle(grid,h,w):
    re=0
    hist=[[0]*(w+1) for i in range(h)]
    for j in range(w):
        if C[0][j]==0:
            hist[0][j]=1
    for j in range(w):
        for i in range(1,h):
            if C[i][j]==1:continue
            hist[i][j]=hist[i-1][j]+1
    for i in range(h):
        re=max(re,stack_processing_of_rectangle(hist[i]))
    return re

def stack_processing_of_rectangle(hist):
    
    maxrect=0
    stack=[]
    for j in range(w+1):
        if not stack:
            stack.append((hist[j],j))
        elif stack[-1][0]<hist[j]:
            stack.append((hist[j],j))
        elif stack[-1][0]>hist[j]:
            while stack and stack[-1][0]>hist[j]:
                hi,wi=stack.pop()
                maxrect=max(maxrect,hi*(j-wi))
            stack.append((hist[j],wi))
    return maxrect

print(Largest_Rectangle(C,h,w))

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda:sys.stdin.readline().rstrip()

def max_rect_in_hist(Hist):
    Hist.append(0)
    ans=0
    Q=[(-1,0)]
    for i,h in enumerate(Hist):
        while(Q[-1][1]>h):
            i0,h0=Q.pop()
            ans=max(ans,h0*(i-Q[-1][0]-1))
        if(Q[-1][1]<=h):
            Q.append((i,h))
    return ans

def resolve():
    h,w=map(int,input().split())
    C=[list(map(lambda x:1-int(x),input().split())) for _ in range(h)]
    from itertools import product
    for i,j in product(range(h-1),range(w)):
        if(C[i+1][j]): C[i+1][j]+=C[i][j]
    print(max(max_rect_in_hist(c) for c in C))
resolve()

Solution (Python):
H, W = map(int, input().split())
height = W * [0]
max_area = 0
for _ in range(H):
    height = [0 if t else height[j]+1 for j, t in enumerate(map(int, input().split()))]
    height.append(0)
    stack = []
    for i, h in enumerate(height):
        if stack:
            if stack[-1][1] == h:
                continue
            elif stack[-1][1] > h:
                while stack and (stack[-1][1] >= h):
                    i_stack, h_stack = stack.pop()
                    max_area = max(max_area, (i - i_stack) * (h_stack))
                i = i_stack
                
            
        stack.append((i, h))
        
print(max_area)

Solution (Python):

class Stack():
    def __init__(self):
        self.stack = []
    
    def push(self, item):
        self.stack.append(item)
    
    def pop(self):
        return self.stack.pop()
    
    def get_stack(self):
        return self.stack
    
    def isEmpty(self):
        return len(self.stack) == 0
    
    def count(self):
        return len(self.stack)
    
    def top(self):
        return self.stack[-1]


def Histogram(n,l):
    if n == 0:
        return 0
    stack = Stack()
    t = 0
    ans = 0
    while t < n:
        r = l[t]
        if stack.isEmpty():
            stack.push((r,t))
            t += 1
            
        elif stack.top()[0] < r:
            stack.push((r,t))
            t += 1
            
        elif stack.top()[0] == r:
            t += 1
            
        elif stack.top()[0] > r:
            while stack.top()[0] > r:
                p,q = stack.pop()
                ans = max(ans,p*(t-q))
                
                if stack.isEmpty():
                    break;
            stack.push((r,q))
            t += 1
    while not stack.isEmpty():
        p,q = stack.pop()
        ans = max(ans, p*(t-q))
        
    return ans


H,W  = [int(_) for _ in input().split()]
dp = [[0]*W for _ in range(H)]
for i in range(H):
    for j,value in enumerate([int(_) for _ in input().split()]):
        dp[i][j] = value
c = 1
for j in range(W):
    i = 0
    while i < H:
        if dp[i][j] == 0:
            dp[i][j] = c
            c += 1
        else:
            dp[i][j] = 0
            c = 1
        i += 1
    c = 1




ans = 0
l = []
for i in range(H):
    for j in range(W):
        if dp[i][j] == 0:
            ans = max(ans,Histogram(len(l),l))
            
            l = []
        else:
            l.append(dp[i][j])
    ans = max(ans,Histogram(len(l),l))
    
    l = []
print(ans)

Solution (Python):
from pprint import PrettyPrinter

pp = PrettyPrinter()


def read_tiles(h, w):
    c = []
    for _ in range(h):
        c.append([int(x) for x in input().split()])
    return c


def make_histogram(h, w, c):
    hg = [[None] * w for _ in range(h)]
    for j in range(w):
        hg[0][j] = 1 if c[0][j] == 0 else 0
    for i in range(1, h):
        for j in range(w):
            hg[i][j] = hg[i - 1][j] + 1 if c[i][j] == 0 else 0
    return hg


def largest_rectangle(h, w, c):
    lr = 0
    hg = make_histogram(h, w, c)
    
    s = []
    for i in range(h):
        hg[i] += [0]
        for j in range(w + 1):
            if len(s) == 0:
                if hg[i][j] > 0:
                    s.append((hg[i][j], j))
            else:
                top = s[-1]
                if top[0] < hg[i][j]:
                    s.append((hg[i][j], j))
                elif hg[i][j] == top[0]:
                    pass
                else:
                    while len(s) > 0 and s[-1][0] >= hg[i][j]:
                        top = s.pop()
                        lr = max(lr, top[0] * (j - top[1]))
                    s.append((hg[i][j], top[1]))
            
    return lr


def main():
    h, w = map(int, input().split())
    c = read_tiles(h, w)
    print(largest_rectangle(h, w, c))


main()

Solution (Python):
h, w = map(int, input().split( ))

c=[[0 for _ in range(w)]]
DP = [[0 for _ in range(w+1)] for __ in range(h+1)]
for _ in range(h):
    c_tmp = list(map(int, input().split( )))
    c.append(c_tmp)


for i in range(w):
    for j in range(1,h+1):
        if c[j][i] == 1:
            DP[j][i] = 0
        else:
            DP[j][i] = DP[j-1][i]+1



S = []
ans = []
Tst =  [[0 for _ in range(w)] for __ in range(h+1)]
for j in range(1,h+1):
    
    for i in range(w+1):
        if len(S) > 0:
            if S[-1][0] <= DP[j][i]:
                S.append([DP[j][i],1])
            
            else:
                tmp = 0
                while len(S) > 0 and S[-1][0] > DP[j][i]:
                    pp = S.pop()
                    tmp += pp[1]
                    ans.append(pp[0]*tmp)
                    Tst[j][i-1] = pp[0]*tmp
                S.append([DP[j][i],tmp+1])
                
        else:
            S.append([DP[j][i],1])




try:
    print(max(ans))
except:
    print(0)

Solution (Python):
from typing import List, Tuple


def rectangle(max_width: int, hist: List[int]) -> int:
    stack: List[Tuple[int, int]] = []  
    ans = 0
    for i, h in enumerate(hist):
        j = i
        while stack and stack[-1][0] > h:
            pre_h, j = stack.pop()
            ans = max(ans, (i - j) * pre_h)

        if not stack or stack[-1][0] < h:
            stack.append((h, j))

    ans = max(ans, max((max_width - j) * h for h, j in stack))
    return ans


if __name__ == "__main__":
    H, W = map(lambda x: int(x), input().split())
    hist = [0] * W

    result = 0
    for _ in range(H):
        one_row = list(map(int, input().split()))
        hist = list(map(lambda pre, cur: (pre + 1) * (cur ^ 1), hist, one_row))
        result = max(result, rectangle(W, hist))

    print(result)

Solution (Python):


import sys
from collections import deque

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

H,W=MAP()
grid=[None]*H
for i in range(H):
    grid[i]=LIST()


acc=list2d(H, W, 0)
for j in range(W):
    if grid[0][j]!=1:
        acc[0][j]=1
for j in range(W):
    for i in range(1, H):
        if grid[i][j]!=1:
            acc[i][j]=acc[i-1][j]+1

for i in range(H):
    acc[i].append(0)

mx=0

for i, hist in enumerate(acc):
    stack=deque()
    for j, h in enumerate(hist):
        if not len(stack):
            stack.append((j, h))
        else:
            if stack[-1][1]<h:
                stack.append((j, h))
            elif stack[-1][1]>h:
                
                while len(stack) and stack[-1][1]>h:
                    prev=stack.pop()
                    w2=j-prev[0]
                    h2=prev[1]
                    mx=max(mx, h2*w2)
                stack.append((prev[0], h))
print(mx)

Solution (Python):

"""
Pattern - Largest Rectangle
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_3_B&lang=jp

"""
import sys


def solve(H, W, grid):
    def calc_hist(m):
        ans = [[0] * W for _ in range(H)]
        for y, row in enumerate(m):
            for x, ch in enumerate(row):
                if ch == '0':
                    ans[y][x] = ans[y - 1][x] + 1 if y > 0 else 1
        return ans

    def calc_area(hist):
        stack = []
        area, left = 0, 0
        for x, h in enumerate(hist):
            if not stack or stack[-1][0] < h:
                stack.append((h, x))
            elif stack[-1][0] > h:
                while stack and stack[-1][0] >= h:
                    hh, left = stack.pop()
                    area = max(area, hh*(x-left))
                stack.append((h, left))
        return area

    hist = calc_hist(grid)
    ans = 0
    for y in range(H):
        ans = max(ans, calc_area(hist[y]+[0]))
    return ans


def main(args):
    H, W = map(int, input().split())
    grid = [input().replace(' ', '') for _ in range(H)]
    ans = solve(H, W, grid)
    print(ans)


if __name__ == '__main__':
    main(sys.argv[1:])

Solution (Python):
H, W = map(int, input().split())
c = []
for _ in range(H):
    *w, = map(int, input().split())
    c.append(w)


t = []
for _ in range(H+2):
    t.append([0]*(W+2))

for w in range(1, W+1):
    for h in range(1, H+1):
        if c[h-1][w-1] == 1:
            t[h][w] = 0
        else:
            t[h][w] = t[h-1][w]+1

ans = 0
for h in range(1, H+1):
    s = []
    for w in range(1, W+2):
        if len(s) == 0 or s[-1][0] < t[h][w]:
            s.append([t[h][w], w])
        elif s[-1][0] > t[h][w]:
            li = w
            while len(s) > 0 and s[-1][0] >= t[h][w]:
                r = s.pop(-1)
                tmp = (w-r[1])*r[0]
                if tmp > ans:
                    ans = tmp
                li = r[1]
            s.append([t[h][w], li])
print(ans)

Solution (Python):
def rectangle(n, hs):
  stack = [] 
  ans = 0
  for i, h in enumerate(hs):
    j = i
    while stack and stack[-1][0] > h:
      pre_h, j = stack.pop()
      ans = max(ans, (i - j) * pre_h)

    if not stack or stack[-1][0] < h:
      stack.append((h, j))

  ans = max(ans, max((n-j) * h2 for h2, j in stack))

  return ans

H, W = map(int, input().split())


hist = [0] * W
result = 0
for _ in range(H):
  ht = list(map(int, input().split()))
  hist = list(map(lambda pre, cur: (pre+1) * (cur ^ 1), hist, ht))
  result = max(result, rectangle(W, hist))
print(result)

Solution (Python):


def rectangle(n, hs):
    stack = []  
    ans = 0
    for i, h in enumerate(hs):
        j = i
        while stack and stack[-1][0] > h:
            pre_h, j = stack.pop()
            ans = max(ans, (i - j) * pre_h)

        if not stack or stack[-1][0] < h:
            stack.append((h, j))

    ans = max(ans, max((n - j) * h2 for h2, j in stack))

    return ans


H, W = map(int, input().split())
hist = [0] * W
result = 0
for _ in range(H):
    ht = list(map(int, input().split()))
    hist = list(map(lambda pre, cur: (pre + 1) * (cur ^ 1), hist, ht))
    result = max(result, rectangle(W, hist))

print(result)

Solution (Python):
class Rectangle:
    def __init__(self, height, pos):
        self.height = height
        self.pos = pos


def getLargestRectangleInRow(size, buffer):
    s = []
    maxv = 0
    buffer.append(0)
    for i in range(size + 1):
        rect = Rectangle(buffer[i], i)
        if len(s) == 0:
            s.append(rect)
        else:
            if s[-1].height < rect.height:
                s.append(rect)
            elif s[-1].height > rect.height:
                target = i
                while len(s) != 0 and s[-1].height >= rect.height:
                    pre = s.pop()
                    area = pre.height * (i - pre.pos)
                    maxv = max(maxv, area)
                    target = pre.pos
                rect.pos = target
                s.append(rect)

    return maxv


def getLargestRectangle(H, W, buffer):
    t = [[0] * W for i in range(H)]
    for i in range(H):
        for j in range(W):
            if buffer[i][j] == 1:
                t[i][j] = 0
            else:
                if i > 0:
                    t[i][j] = t[i-1][j] + 1
                else:
                    t[i][j] = 1

    maxv = 0
    for i in range(H):
        maxv = max(maxv, getLargestRectangleInRow(W, t[i]))
    return maxv



if __name__ == '__main__':
    h, w = [int(v) for v in input().split()]
    c = []
    for i in range(h):
        c.append([int(v) for v in input().split()])

    print(getLargestRectangle(h, w, c))