进行二次搜，一次从i点往左搜，直到找到一点被i点小的点，然后一次往右搜。

//2121252  	2010-03-22 11:20:55  	  Time Limit Exceeded  	1985  	C++  	1001  	0
//2121270  	2010-03-22 11:35:38  	  Accepted  	1985  	C++  	100  	1356
#include <iostream>
#include <cstdio>
using namespace std;

const int MAXSIZE = 100002;

int h[MAXSIZE];
int l[MAXSIZE],r[MAXSIZE];

int main()
{
	int n;
	int i;
	long long ans, tans;
	long long xx = 1;
	while(scanf("%d", &n) && n)
	{
		for(i = 0; i < n; i++)
		{
			scanf("%d", h + i);
		}
		ans = 0;

		//left search
		for(i = 0; i < n; i++)
		{
			l[i] = i;
			while(l[i] > 0 && h[i] <= h[l[i] - 1])
			{
				l[i] = l[l[i] - 1];
			}
		}

		//right search
		for(i = n - 1; i >= 0; i--)
		{
			r[i] = i;
			while(r[i] < n - 1 && h[i] <= h[r[i] + 1] )
			{
				r[i] = r[r[i] + 1];
			}
			tans = xx * h[i] * (r[i] - l[i] + 1);
			//这里必须乘一个long long的数，否则超范围了唉（WA）
			if(ans < tans)
				ans = tans;
		}
		//cout<<ans<<endl;
		printf("%lld\n", ans);
	}
	return 0;
}

• 相关文章
• 全局相关文章