题目链接：https://nanti.jisuanke.com/t/38228
题意：在给出的序列里面找一个区间，使区间最小值乘以区间和得到的值最大，输出这个最大值。
思路：我们枚举每一个数字，假设是a[i]，那么我们就要找一个包含a[i]的区间，并且这个区间里面的最小值就是a[i]，使a[i]乘以这个区间的区间和最大，一直更新这个最大值就可以了。
要保证区间最小值为a[i]，那么就要找下标i左边第一个小于a[i]的数字所在下标和右边第一个小于a[i]的数字下标，我们在这两个下标围成的区间里面找最优的区间和，这个用单调栈，线段树什么的都可以做到，这里用单调栈，因为最快，是线性的。求出每一个数字左右两边第一个比他小的数字下标。L[i]表示左边第一个比a[i]小的数字下标，R[i]表示右边第一个比a[i]小的数字下标，s是一个栈，里面存的是下标。
代码：
//单调栈找每个数字左右两边比自己小的数字位置
for(int i=;i<=n;i++){
while(!s.empty()&&a[s.top()]>a[i]){//在保证栈不为空的情况下把栈顶大于a[i]的
//元素弹出，并把R[s.top()]赋值为i
R[s.top()]=i;
s.pop();
}
if(!s.empty()){//如果栈不为空，那么栈顶有比a[i]小的数字
if(a[s.top()]!=a[i])//如果这个栈顶数字不是a[i]，L[i]=s.top()
L[i]=s.top();
else //如果栈顶数字也是自己，那么向右递推，L[i]=L[s.top()]
L[i]=L[s.top()];
}
else
L[i]=;//栈为空，没有小于a[i]的数字
s.push(i);//把当前数字压入栈
}
while(!s.empty()){
R[s.top()]=n+;
s.pop();
}
我们用前缀和建线段树，一个叶子节点代表一个前缀和。
如果a[i]是一个正数，那么这个区间就要是a[i]为区间最小值，并且区间和尽量大。我们在区间[L[i]，i-1]里找一个最小的前缀和，在区间[i，R[i]-1]里找一个最大的前缀和，用最大的减最小的就得到了包含a[i]的最大区间和。
如果a[i]是一个负数，那么这个区间就要是a[i]为区间最小值，并且区间和尽量小。我们在区间[L[i]，i-1]里找一个最大的前缀和，在区间[i，R[i]-1]里找一个最小的前缀和，用最小的减最大的就是包含a[i]的最小区间和。
然后一直更新就可以了，最后注意n最大是5乘10的5次方...
代码：
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
#include<map>
#include<stack>
#include<cmath>
#include<vector>
#include<set>
#include<cstdio>
#include<string>
#include<deque>
using namespace std;
typedef long long LL;
#define eps 1e-8
#define INF 0xfffffffffffff
#define maxn 500005
int a[maxn],L[maxn],R[maxn];
LL sum[maxn];
int n,m,k,t;
stack<int>s;
struct node{
LL Max,Min;
}tree[maxn<<];
void update(int k){
tree[k].Max=max(tree[k<<].Max,tree[k<<|].Max);
tree[k].Min=min(tree[k<<].Min,tree[k<<|].Min);
}
void build(int l,int r,int k){//建树
if(l==r){
tree[k].Max=tree[k].Min=sum[l];
return;
}
int mid=(l+r)/;
build(l,mid,k<<);
build(mid+,r,k<<|);
update(k);
}
LL ask_Max(int l,int r,int k,int L,int R){
if(l>=L&&r<=R){
return tree[k].Max;
}
int mid=(l+r)/;
LL ans=-INF;
if(L<=mid)
ans=max(ans,ask_Max(l,mid,k<<,L,R));
if(R>mid)
ans=max(ans,ask_Max(mid+,r,k<<|,L,R));
return ans; }
LL ask_Min(int l,int r,int k,int L,int R){
if(l>=L&&r<=R){
return tree[k].Min;
}
int mid=(l+r)/;
LL ans=INF;
if(L<=mid)
ans=min(ans,ask_Min(l,mid,k<<,L,R));
if(R>mid)
ans=min(ans,ask_Min(mid+,r,k<<|,L,R));
return ans; }
int main()
{
while(scanf("%d",&n)!=EOF){
while(!s.empty())
s.pop();
sum[]=;
for(int i=;i<=n;i++){
scanf("%d",&a[i]);
sum[i]=sum[i-]+a[i];
}
//单调栈找每个数字左右两边比自己小的数字位置
for(int i=;i<=n;i++){
while(!s.empty()&&a[s.top()]>a[i]){//在保证栈不为空的情况下把栈顶大于a[i]的
//元素弹出，并把R[s.top()]赋值为i
R[s.top()]=i;
s.pop();
}
if(!s.empty()){//如果栈不为空，那么栈顶有比a[i]小的数字
if(a[s.top()]!=a[i])//如果这个栈顶数字不是a[i]，L[i]=s.top()
L[i]=s.top();
else //如果栈顶数字也是自己，那么递推，L[i]=L[s.top()]
L[i]=L[s.top()];
}
else
L[i]=;//栈为空，没有小于a[i]的数字
s.push(i);//把当前数字压入栈
}
while(!s.empty()){
R[s.top()]=n+;
s.pop();
} build(,n,);
LL ans=-INF;
for(int i=;i<=n;i++){
if(a[i]>=){//a[i]大于等于0，求左边最小的前缀和，右边最大的前缀和，右边减左边，得到包含a[i]的最大区间和
LL Min=ask_Min(,n,,L[i],i-);
LL Max=ask_Max(,n,,i,R[i]-);
ans=max(ans,a[i]*(Max-Min));
}else{//a[i]小于0，求左边最大的前缀和，右边最小的前缀和，右边减左边，得到包含a[i]的最小区间和
LL Min=ask_Min(,n,,i,R[i]-);
LL Max=ask_Max(,n,,L[i],i-);
ans=max(ans,a[i]*(Min-Max));
}
}
printf("%lld\n",ans);
}
return ;
}