1506.cpp

来自「杭电 acm部分代码 有兴趣的可以下载 谢谢」· C++ 代码 · 共 43 行

#include <stdio.h>
long h[100010];
long l[100010];
long r[100010];
long i, n;
__int64 max, num;
int main()
{
	while (scanf("%d", &n) == 1 && n)
	{
		for (i = 0; i < n; i++)
		{
			scanf("%ld", &h[i]);
			r[i] = l[i] = i;
		}
		for (i = 1; i < n; i++)
		{
			while (l[i] > 0 && h[l[i] - 1] >= h[i])
			{
				l[i] = l[l[i] - 1];
			}
		}
		for (i = n - 2; i >= 0; i--)
		{
			while (r[i] < n - 1 && h[r[i] + 1] >= h[i])
			{
				r[i] = r[r[i] + 1];
			}
		}
		max = 0;
		for (i = 0; i < n; i++)
		{
			num = (__int64)h[i] * (r[i] - l[i] + 1);
			if (num > max)
			{
				max = num;
			}
		}
		printf("%I64d\n", max);
	}
	return 0;
}