pku2559.cpp

来自「这是ACM 方面的资料 是PKU的 北京大学的出来的」· C++ 代码 · 共 54 行

#include <stdio.h>
#define SIZE 101010

__int64 Num[SIZE];
int pre[SIZE], next[SIZE], stack[SIZE];
int N, top;
__int64 Max, tmp;

int main()
{
	int i, j;
	
	while (scanf("%d", &N) != -1 && N)
	{
		for (i = 0; i < N; i++)
		{
			scanf("%I64d", &Num[i]);
		}
		stack[0] = -1;
		top = 0;
		for (i = 0; i < N; i++)
		{
			while (top != 0 && Num[stack[top]] >= Num[i])
			{
				top--;
			}
			stack[++top] = i;
			pre[i] = stack[top - 1] + 1;
		}
		stack[0] = N;
		top = 0;
		for (i = N - 1; i >= 0; i--)
		{
			while (top != 0 && Num[stack[top]] >= Num[i])
			{
				top--;
			}
			stack[++top] = i;
			next[i] = stack[top - 1] - 1;
		}
		for (i = 0, Max = 0; i < N; i++)
		{
			tmp = (next[i] - pre[i] + 1) * Num[i];
			if (tmp > Max)
			{
				Max = tmp;
			}
		}
		printf("%I64d\n", Max);
	}
	return 0;
}