11873번: 최대 직사각형

https://www.acmicpc.net/problem/11873


$O(tnm)$

http://codedoc.tistory.com/723의 아이디어를 이용하자.
i행의 각 열마다 위로 연속된 1의 개수를 위 문제에서 히스토그램 높이라 생각하고 최대직사각형 넓이를 구한다.
모든 행에서 이러한 방법을 적용했을 때 최대 직사각형 넓이를 찾는다.

#include<cstdio>
#include<algorithm>
using namespace std;
int n, m;
int main() {
    while (scanf("%d%d", &n, &m) && n) {
        int r = 0, h[1001] = { 0, }, stk[1001], top;
        for (int i = 1; i <= n; i++) {
            stk[top = 0] = 0;
            for (int j = 1, x; j <= m; j++) {
                scanf("%d", &x);
                h[j] = (h[j] + 1) * x;
                while (h[stk[top]] > h[j]) r = max(r, (j - stk[top - 1] - 1)*h[stk[top--]]);
                stk[++top] = j;
            }
            while (top) r = max(r, (m - stk[top - 1])*h[stk[top--]]);
        }
        printf("%d\n", r);
    }
    return 0;
}