울타리 잘라내기

알고스팟 문제: https://algospot.com/judge/problem/read/FENCE

algospot.com :: FENCE

입력

첫 줄에 테스트 케이스의 개수 C (C≤50)가 주어집니다. 각 테스트 케이스의 첫 줄에는 판자의 수 N (1≤N≤20000)이 주어집니다. 그 다음 줄에는 N개의 정수로 왼쪽부터 각 판자의 높이가 순서대로 주어집니다. 높이는 모두 10,000 이하의 음이 아닌 정수입니다.

출력

각 테스트 케이스당 정수 하나를 한 줄에 출력합니다. 이 정수는 주어진 울타리에서 잘라낼 수 있는 최대 직사각형의 크기를 나타내야 합니다.

 

(종만북 참고) 코드 

 

#include  <iostream>
#include  <vector>
#include  <algorithm>
using namespace std;
const int MAX = 20000;
int N;
vector h;
int solve(int left, int right)
{
if (left == right) return h[left];

int mid = (left + right) / 2;
int ret = max(solve(left, mid), solve(mid + 1, right)); // 두 부분에 모두 걸치는 사각형 중 가장 큰 것을 찾는다

int lo = mid, hi = mid + 1;

int height = max(h[lo], h[hi]);
ret = max(ret, height * 2); // [mid, mid+1]만 포함하는 너비 2 인 사각형을 고려한다
while (left < lo || hi < right) // 사각형이 경계사이에 있을경우, 입력 전체를 덮을 때까지 확장해 나간다
{ 
if (hi < right && (lo == left || h[lo - 1] < h[hi + 1]))
{
hi++;
height = min(height, h[hi]);
}
else
{
lo--;
height = min(height, h[lo]);
}
ret = max(ret, (hi - lo + 1) * height);
}
return ret;
}
int main()
{
int C;
cin >> C;
while (C--)
{
h.clear();
cin >> N;
for (int i = 0; i < N; ++i)
{
int height;
cin >> height;
h.push_back(height);
}
int answer;
answer = solve(0, N - 1);
cout << answer << endl;
}
return 0;
}