Sau đây là cách tìm hình chữ nhật lớn nhất trong thời gian \(O(n2)\):

Với mỗi ô \(j\) trên hàng \(i\), ta tìm \(f(j)\) là số ô 1 liên tiếp trên cột \(j\), tính từ hàng \(i\) trở lên. Sau đó, với mỗi cột \(j\), ta tiếp tục tìm ô gần nhất bên trái và ô gần nhất bên phải có \(f\) nhỏ hơn \(f(j)\), sau đó tính diện tích hình chữ nhật ở cột \(j\) là \(S=f(j)×(r−l−1)\) với \(l,r\) là chỉ số 2 ô bên trái và bên phải nói trên.

Hình minh hoạ khi tính f(4):

Để tìm \(l,r\) nhanh, ta dùng kĩ thuật sử dụng
Deque tìm Min/Max trên đoạn tịnh tiến

Nguồn: vietcodes