HDU 1506 Largest Rectangle in a Histogram 分治法 -

题目地址：http://acm.hdu.edu.cn/showproblem.php?pid=1506

分治法，分成左边和右边和中间

求中间最大面积的时候用贪心，mid出发，左右两边扫描，优先取最高的

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn=100000+5;
typedef long long LL;
const LL INF=0x3f3f3f3f;
LL h[maxn];
LL MaxArea(LL x,LL y)  //[x,y)
{if(y-x==1) return h[x];LL mid=x+(y-x)/2;LL maxa=max(MaxArea(x,mid),MaxArea(mid,y));LL maxA=h[mid],minH=h[mid],pL,pR; pL=mid-1,pR=mid+1;while(pL>=x&&pR<y){if(h[pL]>h[pR]){minH=min(minH,h[pL]);maxA=max(maxA,minH*(pR-pL));pL--;}else {minH=min(minH,h[pR]);maxA=max(maxA,minH*(pR-pL));pR++;}}while(pL>=x) {minH=min(minH,h[pL]);maxA=max(maxA,minH*(pR-pL));pL--;}while(pR<y) {minH=min(minH,h[pR]);maxA=max(maxA,minH*(pR-pL));pR++;}return max(maxA,maxa);
}
int main()
{LL N; while(~scanf("%I64d",&N),N){for(LL i=0;i<N;i++)scanf("%I64d",&h[i]);cout<<MaxArea(0,N)<<endl;}return 0;
}