CSP 201312-3 最大的矩形思路：代码：

98 阅读 0 评论 65 点赞

我是靠谱客的博主故意朋友，最近开发中收集的这篇文章主要介绍CSP 201312-3 最大的矩形思路：代码：，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

思路：

1.对于每一个宽度为1的矩形，尝试以它为高，然后寻找宽度；
2.先向左寻找，找到一个高度比它高或等于他的，就记录下来，直到找到宽度比它低的；
3.向右进行同样的操作；
4.比较出最大的面积；

代码：

#include<iostream>
using namespace std;
int n,h[1001],maxs=0,len[1001];
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&h[i]);
	for(int i=1;i<=n;i++){
		for(int j=i;j>=1;j--)
			if(h[j]>=h[i]) len[i]++;
			else break;
		for(int j=i+1;j<=n;j++)
			if(h[j]>=h[i]) len[i]++;
			else break;
	}
	for(int i=1;i<=n;i++){
		int s=h[i]*len[i];
		if(s>maxs) maxs=s;
	}
	printf("%d",maxs);
	return 0;
}