记录编号	610867	评测结果	A
题目名称	[POJ 2559]直方图中最大的矩形	最终得分	100
用户昵称	终焉折枝	是否通过	通过
代码语言	C++	运行时间	0.051 s
提交时间	2026-01-22 20:50:23	内存使用	9.16 MiB

#include<iostream>
#include<stack>
#include<algorithm>
#include<cstring>
using namespace std;

#define int long long
const int MAXN = 1e6 + 10;

int n, a[MAXN];
int l[MAXN], r[MAXN];
int sz[MAXN], in[MAXN];

int dfs(int x){
	if(!x) return 0;
	sz[x] = 1;
	sz[x] += dfs(l[x]);
	sz[x] += dfs(r[x]);
	return sz[x];
}

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	while(cin >> n && n){
		for(int i = 0;i <= n;i ++){
			l[i] = r[i] = sz[i] = in[i] = 0;
		}
		stack<int> st;
		for(int i = 1;i <= n;i ++){
			cin >> a[i];
		}
		for(int i = 1;i <= n;i ++){
			int last = 0;
			while(!st.empty() && a[st.top()] > a[i]){
				last = st.top();
				st.pop();
			}
			if(!st.empty()){
				r[st.top()] = i;
			}
			l[i] = last;
			st.push(i);
		}
		for(int i = 1;i <= n;i ++){
			if(l[i]) in[l[i]] ++;
			if(r[i]) in[r[i]] ++;
		}
		int root = 0;
		for(int i = 1;i <= n;i ++){
			if(!in[i]){
				root = i;
				break;
			}
		}
		dfs(root);
		int ans = 0;
		for(int i = 1;i <= n;i ++){
			ans = max(ans, a[i] * sz[i]);
		}
		cout << ans << '\n';
	}
	return 0;
}