SP1805 HISTOGRA - Largest Rectangle in a Histogram

悬线法预处理 dp。

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define N 100005
int n, a[N], l[N], r[N];
signed main()
{
	while(scanf("%lld", &n) != EOF && n)
	{
		for(int i = 1; i <= n; i++)
		{
			scanf("%lld", &a[i]);
		}
		for(int i = 1; i <= n; i++)
		{
			if(i == 1)
			{
				l[i] = 1;
				continue;
			}
			int pos = i - 1;
			for(; pos >= 1; pos--)
			{
				if(a[i] > a[pos])
				{
					break;
				}
				else
				{
					pos = l[pos];
				}
			}
			l[i] = pos + 1;
		}
		for(int i = n; i >= 1; i--)
		{
			if(i == n)
			{
				r[i] = n;
				continue;
			}
			int pos = i + 1;
			for(; pos <= n; pos++)
			{
				if(a[i] > a[pos])
				{
					break;
				}
				else
				{
					pos = r[pos];
				}
			}
			r[i] = pos - 1;
		}
		int ans = 0;
		for(int i = 1; i <= n; i++)
		{
			ans = max(ans, a[i] * (r[i] - l[i] + 1));
		}
		printf("%lld\n", ans);
	}
	return 0;
}