히스토그램은 직사각형 여러 개가 아래쪽으로 정렬되어 있는 도형이다. 각 직사각형은 같은 너비를 가지지만, 높이는 서로 다를 수 있다. 아래는 높이가 2, 1, 4, 5, 1, 3, 3이고 너비가 1인 직사각형으로 이루어진 히스토그램이며 색칠된 부분은 가장 넓은 직사각형이다. 위와 같이 가장 넓은 직사각형을 구하기 위해서는 다음과 같은 알고리즘을 적용할 수 있다. 이때 히스토그램의 각 부분(2, 1, 4, 5, 1, 3, 3의 높이를 가지는 객체)를 ‘막대기’라고 부르자. 모든 막대기 중에 가장 낮은 높이의 막대기를 선택한다. (가장 낮은 높이) × (막대기의 개수)를 통해 현재 히스토그램에서 가장 낮은 높이의 직사각형의 넓이를 구한다. 가장 낮은 높이의 막대기를 기준으로 왼쪽과 오른쪽으로 나눈다. 각 부..
