题解 | #编程题2#

单调栈的模板题
如果你做过leetcode的柱状图中最大的矩形。
枚举元素ai为区间最小值，显然区间越大越好，因此对ai向左右分别找到第一个小于ai的值，此区间即为选择ai为最小值时最大值。
枚举a1...an，题目可解。
#include <bits/stdc++.h>
#define maxn 500005
typedef long long ll;
using namespace std;
int n,a[maxn],l[maxn],r[maxn];
ll ans,sum[maxn];
int main()
{
ios::sync_with_stdio(0),cin.tie(0);
int i,j;
cin>>n;
for(i=1; i<=n; i++)
cin>>a[i],sum[i]=sum[i-1]+a[i];
stack<int>st;
for(i=1; i<=n; i++)
{
while(st.size()&&a[st.top()]>=a[i])
st.pop();
if(st.empty())
l[i]=0;
else
l[i]=st.top();
st.push(i);
}
while(st.size())st.pop();
for(i=n;i>=1;i--)
{
while(st.size()&&a[st.top()]>=a[i])
st.pop();
if(st.empty())
r[i]=n+1;
else
r[i]=st.top();
st.push(i);
}
for(i=1;i<=n;i++)
ans=max(ans,1LLa[i](sum[r[i]-1]-sum[l[i]]));
cout<<ans;</int>

return 0;

}