java ccf最大的矩形,最大的矩形（ccf）

某年ccf比赛题，ccf测试数据很独特，并且是根据你做正确的测试数据给分的，想要得满分，就一定不能放过任何一个优化的点

题目描述：

在横轴上放了n个相邻的矩形，每个矩形的宽度是1，而第i(1 ≤ i ≤ n)个矩形的高度是hi。这n个矩形构成了一个直方图。例如，下图中六个矩形的高度就分别是3, 1, 6, 5, 2, 3。

请找出能放在给定直方图里面积最大的矩形，它的边要与坐标轴平行。对于上面给出的例子，最大矩形如下图所示的阴影部分，面积是10。

输入格式

第一行包含一个整数n，即矩形的数量(1 ≤ n ≤ 1000)。

第二行包含n 个整数h1, h2, … , hn，相邻的数之间由空格分隔。(1 ≤ hi ≤ 10000)。hi是第i个矩形的高度。

输出格式

输出一行，包含一个整数，即给定直方图内的最大矩形的面积。

样例输入

6

3 1 6 5 2 3

样例输出

10

解题思路：

一、开始想的是能否通过动态规划的思路解决本题，保留到达当前点时所有高度的最大值。这样我就拥有所有满足矩形条件的数据组(起点、重点、高)这个算法的时间复杂度为n*max(即h高度)。

二、但是本题高度峰值是10000  而n是1000，与其相比，时间效率可能还不如单向遍历枚举法，简单粗暴的枚举所有的起点和终点再乘以最小的高，这样时间复杂度为n*n。

三、顺着单向遍历的思路继续思考，权值是由高和长来决定的，长度无疑是遍历所有矩形，那么我们是否可以直接就限制我们的高呢。

即：我们假定一个包含最优解的某点i，某点不是起始点，也不是重点，他的高为a[i]，那么由他向两边扩展，他扩展的所有点其高(a[i+1],a[i-1]……)都大于a[i]，那么这个相连的矩阵就是最大的矩阵了。同时，这是一个双向的遍历，循环在到达顶端及存在一个小与a[i]的高就结束。那么这个循环在大多数情况下都不会太长。其复杂度就是n*d，d很小

#include/*                      n*max动态规划算法 __int64 dp[1010][10010];int main(){int n,i,j;__int64 x,max;int a[1010];while(scanf("%d",&n)!=EOF){max=0;for(i=1;i<=n;i++){scanf("%d",&a[i]);if(a[i]>max)max=a[i];    }    for(i=1;i<=n;i++)for(j=1;j<=max;j++)dp[i][j]=0;    x=max;for(i=1;i<=n;i++)for(j=1;j<=a[i];j++){if(j<=a[i-1])dp[i][j]=dp[i-1][j]+j;elsedp[i][j]=j;if(dp[i][j]>x)x=dp[i][j];    }    printf("%I64dn",x);        }return 0;}*//*                     n*n单向遍历算法 #includeint fmax(int a,int b){return a>b?a:b;}int fmin(int a,int b){return a     //n*d(d很小)双向遍历算法 int fmax(int a,int b){return a>b?a:b;}int fmin(int a,int b){return a=a[i]){    x++;    r++;}while(l>=1&&a[l]>=a[i]){    x++;    l--;}x=x*a[i];max=fmax(x,max);}printf("%dn",max);}return 0;}