컴공과컴맹효묘의블로그

https://www.acmicpc.net/problem/1725 입력이 10만이라, O(N^2)은 시간 내 풀이가 불가능합니다. "이 직사각형의 밑변은 항상 히스토그램의 아랫변에 평행하게 그려져야한다." 에서 아래쪽 밑변은 히스토그램의 아랫변과 겹치게 그리는 것이 항상 최대이고, 위쪽 밑변은 직사각형이 포함하는 막대들의 높이 중 최소인 막대의 윗변과 겹쳐야합니다. O(NlogN)가 걸리는 분할정복으로 풀어봤습니다.하나의 히스토그램을 절반으로 잘라서 왼쪽의 최대와 오른쪽의 최대, 그리고 중간을 포함하는 큰 히스토그램의 최대를 구하여 비교합니다.중간을 포함하는 큰 히스토그램은 투 포인터로 O(N)이 걸립니다. left와 right를 각각 mid, mid+1로 초기화 하고 left-1, right+1의 높이..