博客

1102 面积最大的矩形(简单DP)

  • Post author:
  • Post category:其他


1.Question:

有一个正整数的数组，化为直方图，求此直方图包含的最大矩形面积。例如 2,1,5,6,2,3，对应的直方图如下：
面积最大的矩形为5,6组成的宽度为2的矩形，面积为10

2.Solution:

DP思想，和小学期做的编程珠玑那道题基本上是一个套路
定义状态：
left[i]:i矩形的左边界
right[i]:i举行的右边界
状态转移方程:
right和left是对称的，这里只说left 
if(data[i]>data[i-1]) left[i]=i;
else 
{
    for(j=left[i-1];j>=1&&data[j]<data[i];j--);
    left[i]=j+1;
}

在上面的状态转移的过程中，虽然我们加快了回溯左边界的过程，但是并没有找到，还是要我们回去继续查找的，但是已经加快了速度了

3.Code:

#include"iostream"
#include"cstdio"
#include"cstring"
#define ll long long
#define N 50005

using namespace std;

int n;
ll data[N];
int leftp[N];
int rightp[N];
int j; 

int main()
{
	memset(rightp,0,sizeof(rightp));
	memset(leftp,0,sizeof(leftp));
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%lld",&data[i]);
	leftp[1]=1;
	for(int i=2;i<=n;i++)
	{
		if(data[i]>data[i-1]) leftp[i]=i;
		else
		{
			for(j=leftp[i-1]-1;j>=1;j--) if(data[j]<data[i]) break;
			leftp[i]=j+1;
		}
	}
	rightp[n]=n;
	for(int i=n-1;i>=1;i--)
	{
		if(data[i]>data[i+1]) rightp[i]=i;
		else
		{
			for(j=rightp[i+1]+1;j<=n;j++) if(data[j]<data[i]) break;
			rightp[i]=j-1;
		}
	}
	ll maxp=0;
	for(int i=1;i<=n;i++)
	{
		ll k=(rightp[i]-leftp[i]+1)*data[i];
		maxp=maxp>k?maxp:k;
	}
	printf("%lld\n",maxp);
	return 0;
}


版权声明：本文为ltyqljhwcm原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。