다음의 문제가 동적 프로그래밍이 활용되는 문제 중 하나다.
문제 해결 접근: 최대 히스토그램 넓이 기반
임의의 높이를 가진 N 개의 막대가 주어질 때, 막대 안에 포함되는 직사각형 중 가장 넓이가 큰 직사각형의 넓이를 구하는 유명한 문제다.
풀 수 있는 다양한 방법이 있는데, 대표적인 방법들에 대해서 알아본다.
브루트포스
시간복잡도 : O( N^3 )
우선 알고리즘의 효율성에 대해 생각하지 말고 가장 무식한 방법을 떠올려보자. 만들 수 있는 모든 직사각형을 만들어 직사각형의 넓이를 구하면 답을 계산할 수 있을 것이다. 모든 직사각형은 자신의 가장 왼쪽에 위치한 막대와 가장 오른쪽에 위치한 막대가 있을 것이다. 그 직사각형의 높이는 위치상 직사각형에 포함되는 막대들의 높이 중 가장 낮은 막대의 높이가 될 것이다. 그렇기 때문에 모든 막대 쌍 l, r 에 대해 l 부터 r 까지의 막대 중 가장 높이가 낮은 막대의 높이를 계산한 뒤 직사각형의 넓이를 계산해 답을 갱신하면 문제를 해결할 수 있다.
모든 막대 쌍을 순회하는 데 O(N2)O(N2) 의 시간이 소요되고, 각 막대 쌍에 대해 최대 높이를 구하는데 O(N)O(N) 의 시간이 소요되므로, 총 O(N3)O(N3) 의 시간이 소요된다.