: 어떤 판자를 완전히 포함하는 사각형 중 면적이 최대인 사각형을 해당 판자의 최대 사각형이라고 부르자.
: 이 사각형에는 다음과 같은 특징이 있다.
•
이 사각형의 높이는 i번 판자와 항상 같다.
•
이 사각형의 왼쪽 끝과 오른쪽 끝은 i번 판자보다 낮은 판자들로 막혀있다. 그리고 이 판자들을 각각 left[i], right[i]로 부른다.
: left[i], right[i]를 알고 있다면 최대 사각형의 넓이는 간단하게 구할 수 있다.
: 하지만 left[i], right[i]를 찾는 간단한 알고리즘을 수행하는 데에는 판자의 개수에 비례하는 시간이 소요된다. 그러면 알고리즘은 O(N^2)의 시간에 수행되기 때문에 분할정복보다도 못한 결과를 가져온다.
: 어떻게 해야 모든 판자에 대해 left[i], right[i]를 상수 시간에 계산할 수 있을까? 열쇠는 각 판자들을 각각 계산하는 것이 아니라 다른 판자를 계산했던 정보를 활용하는 것이다.
