가장 큰 정사각형
면접 대비시간 제한1초메모리 제한128 MB
0과 1로 이루어진 격자에서 모든 칸이 1인 가장 큰 정사각형의 면적을 동적 계획법으로 구합니다.
문제
0과 1로 이루어진 n x m 격자가 주어진다. 격자 안에서 모든 칸이 1인 정사각형 중 넓이가 가장 큰 것을 찾아라.
출력해야 하는 값은 정사각형의 한 변의 길이가 아니라 넓이이다.
입력
첫째 줄에 두 정수 n, m이 주어진다. (1 <= n, m <= 1,000)
다음 n개의 줄에는 0과 1로 이루어진 길이 m의 문자열이 하나씩 주어진다.
출력
첫째 줄에 모든 칸이 1인 가장 큰 정사각형의 넓이를 출력한다.