有一个直方图，用一个整数数组表示，其中每列的宽度为1，求所给直方图包含的最大矩形面积。比如，对于直方图[2,7,9,4],它所包含的最大矩形的面积为14(即[7,9]包涵的7x2的矩形)。
给定一个直方图A及它的总宽度n，请返回最大矩形面积。保证直方图宽度小于等于500。保证结果在int范围内。
测试样例：
[2,7,9,4,1],5
返回：14
public int countArea(int[] A, int n) {
int dp[][] = new int[n][n];
dp[0][0]=A[0];
for(int i=1;i<n;++i)
dp[0][i]=Math.max(A[i-1],A[i]);
int t,minh,s;
for(int i=1;i<n;++i){
t=n-i;
for(int j=0;j<t;++j){
minh=A[j];
for(int k=1;k<=i;++k){
minh=Math.min(minh, A[j+k]);
}
s = (i+1)*minh;
dp[i][j]=Math.max(dp[i-1][j], dp[i-1][j+1]);
dp[i][j]=Math.max(dp[i][j], s);
if(j>0)
dp[i][j]=Math.max(dp[i][j], dp[i][j-1]);
}
}
return dp[n-1][0];
}
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
