행렬 찾기

• 1로만 이루어진 최대 직사각형 을 찾는 문제. Parcel과도 동일한 문제.
• O(n)의 '히스토그램에서 가장 큰 직사각형 찾기'를 1행~i행 까지로 만든 누적합 배열에 n번 적용하는 방식으로 O(n^2)에 풀수 있다.

"""Solution code for "BOJ 1687. 행렬 찾기".

- Problem link: https://www.acmicpc.net/problem/1687
- Solution link: http://www.teferi.net/ps/problems/boj/1687

Tags: [nge]
"""

from teflib import seqtask


def main():
    N, M = [int(x) for x in input().split()]
    grid = [input() for _ in range(N)]

    answer = 0
    heights = [0] * M
    for row in grid:
        for i, x in enumerate(row):
            heights[i] = heights[i] + 1 if x == '0' else 0
        begs, ends = seqtask.max_ranges_for_each_min(heights)
        max_area = max(h * (e - b) for h, b, e in zip(heights, begs, ends))
        answer = max(max_area, answer)

    print(answer)


if __name__ == '__main__':
    main()

• Dependency: teflib.seqtask.max_ranges_for_each_min