(알고리즘) 분할정복 문제(Divide and Conquer)_울타리 잘라내기

https://algospot.com/judge/problem/read/FENCE

이 문제는 왼쪽과 오른쪽을 나누어서 접근하면 되는 데 문제는
겹치는 부분의 면적을 어떻게 구할 것인지가 문제이다.

이는 오른쪽과 왼쪽으로 1씩 증가시키면서 큰 것을 return 한다.

private static int h[];

private static int solve(int left,int right)
{
if(left==right)return h[left];

int mid=(left+right)/2;

int ret=Math.max(solve(left,mid),solve(mid+1,right));

int lo=mid;
int hi=mid+1;

int minHeight=Math.min(h[lo],h[hi]);

ret=Math.max(ret,2*minHeight);

while(left<lo || hi<right)
{
if(hi<right&&(lo==left || h[hi+1]>h[lo-1]))
{
hi++;
minHeight=Math.min(minHeight,h[hi+1]);
}
else
{
lo--;
minHeight=Math.min(minHeight,h[lo-1]);
}
ret=Math.max(ret,(hi-lo+1)*minHeight);
}
return ret;
}