1525.cpp

这是哈尔滨工业大学acmOJ的源代码

/*  This Code is Submitted by wywcgs for Problem 1525 on 2005-10-30 at 04:11:51 */ 
#include <cstdio>

const long MAX = 102400;

int main()
{
	long stack[MAX], top;
	long left[MAX], right[MAX];
	long i, n;
	long long h[MAX], max, p;

	while(scanf("%ld", &n) == 1) {
		if(n == 0) {
			return 0;
		} else {
			top = 0;
			stack[top++] = 0;
			h[0] = h[n+1] = -1;
			for(i = 1; i <= n; i++) {
				scanf("%lld", &h[i]);
				while(h[stack[top-1]] >= h[i]) {
					top--;
				}
				left[i] = stack[top-1];
				stack[top++] = i;
			}
			top = 0;
			stack[top++] = n + 1;
			max = -1;
			for(i = n; i > 0; i--) {
				while(h[stack[top-1]] >= h[i]) {
					top--;
				}
				right[i] = stack[top-1];
				stack[top++] = i;
				p = (right[i] - left[i] - 1) * h[i];
				if(p > max) {
					max = p;
				}
			}
			printf("%lld\n", max);
		}
	}
	
	return 0;
}