2559.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

#include <stdio.h>

int s[100002];
int h[100002];
int st[100002];
int id[100002],n;

bool init()
{
	int i;
	scanf( "%d", &n );
	if( n == 0 ) return false;

	for( i=0; i<n; i++ )
	scanf( "%d", &h[i] );

	return true;
}

void doit()
{
	int i, m;
	
	st[0] = -1;
	id[0] = -1;
	m = 1;

	for( i=0; i<n; i++ )
	{
		while( st[m-1] > h[i] )
			m--;

		if( st[m-1] == h[i] )
		{
			s[i] = i - id[m-2];
			id[m-1] = i;
		}
		else
		{
			s[i] = i - id[m-1];
			st[m] = h[i];
			id[m] = i;
			m++;
		}
	}
	
	st[0] = -1;
	id[0] = n;
	m = 1;

	for( i=n-1; i>=0; i-- )
	{
		while( st[m-1] > h[i] )
			m--;

		if( st[m-1] == h[i] )
		{
			s[i] += id[m-2] - i;
			id[m-1] = i;
		}
		else
		{
			s[i] += id[m-1] - i;
			st[m] = h[i];
			id[m] = i;
			m++;
		}
	}

	__int64 ans = 0, temp;

	for( i=0; i<n; i++ )
	if( ( temp = (__int64)( s[i] - 1 ) * h[i] ) > ans )
		ans = temp;

	printf( "%I64d\n", ans );

}

int main()
{
	while( init() )
		doit();
	return 0;
}