pku2796.cpp

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

#include <stdio.h>
#define SIZE 101010

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

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