2374638_wa.c

北大大牛代码 1240道题的原代码 超级权威

# include <stdio.h>

__int64  sum[100002], SUM, max;
long i, j, n, a[100002], x, y, left[100002], right[100002];

int main()
{
	while(scanf("%ld",&n)==1&&n)
	{
		sum[0] = 0;
		for(i = 1; i <= n; i++)
		{
			scanf("%ld",&a[i]);
			sum[i] = sum[i-1] + a[i];
			j = i - 1;
			while(j&&a[i] <= a[j])
				j = left[j] - 1;
			left[i] = j + 1;
		}
		for(i = n; i >= 0; i--)
		{
			j = i + 1;
			while(j<=n&&a[i] <= a[j])
				j = right[j] + 1;
			right[i] = j - 1;
		}
		max = -1;
		for(i = 1; i <= n; i++)
		{
			SUM = (right[i] - left[i] + 1)*a[i];
			if(SUM > max)
				max = SUM;
		}
		printf("%I64d\n",max);
	}
	return 0;
}