求木板最大拼接矩形

给定n块木板A[1…n]，高度记为A[i]，每块目标高度不等，宽度相等，用这些木板排列成一面木板墙，木板排列好后，求解木板墙中最大的矩形面积，请设计算法求得木板墙最大的矩形面积，并分析算法效率。 举例说明，如下图所示的木板排列，最大矩形面积为深灰色区域，即4*3=12。 分析： 扫描数组，计算出每个以A[i]为高的矩形面积，再找出最大值即可。 对于A[i]，分别向前和向后扫描，若高度大于等于A[i]，则以A[i]为高的矩形面积加上A[i]. 很显然，算法复杂度为O(n^2).

int get_max(int a[], int n) { int i, j, tmp; int result = a[0]; for (i = 0; i < n; i++) { tmp = a[i]; for (j = i-1; (j >= 0) && (a[j] >= a[i]); j--) { tmp += a[i]; } for (j = i+1; (j < n) && (a[j] >= a[i]); j++) { tmp += a[i]; } if (tmp > result) result = tmp; } return result; }