【美团】最大矩形面积（分治法）
给定一组非负整数组成的数组h，代表一组柱状图的高度，其中每个柱子的宽度都为1。 在这组柱状图中找到能组成的最大矩形的面积（如图所示）。 入参h为一个整型数组，代表每个柱子的高度，返回面积的值。
输入描述:
输入包括两行,第一行包含一个整数n(1 ≤ n ≤ 10000) 第二行包括n个整数,表示h数组中的每个值,h_i(1 ≤ h_i ≤ 1,000,000)
输出描述:
输出一个整数,表示最大的矩阵面积。
示例1
输入
6 2 1 5 6 2 3
输出
10
分治法：最大矩形面积只可能有三种情况：1. 取决于高度最小的柱子，此时面积等于高度乘总长度；2. 最大面积出现在高度最小的柱子左边；3. 最大面积出现在高度最小的柱子右边；'''#include<iostream>
using namespace std;
int sort(int *a,int low,int high)
{
int min=low;
for(int i=low+1;i<=high;i++)
{
if(a[i]<a[min])
min=i;
}
return min;
}
int area(int *a,int low,int high)
{
int pivot;
int area_max;
if(low==high)
return a[low];
else if(low<high)
{
int area_1,area_2,area_3;
pivot=sort(a,low,high);
area_2=(high-low+1)*a[pivot];
area_1=area(a,low,pivot-1);
area_3=area(a,pivot+1,high);
area_max=(area_1>area_2)?area_1:area_2;
area_max=(area_3>area_max)?area_3:area_max;
return area_max;
}
return 0;
}
int main()
{
int N;
while(cin>>N)
{
int * p=new int[N];
for(int i=0;i<N;i++)
cin>>p[i];
int max=area(p,0,N-1);
cout<<max;
}
}