就是求区间和与区间最小值的积的最大值 但是a[i]可能是负的 这就很坑 赛后看了好多dalao的博客 终于a了
这个问题我感觉可以分为两个步骤
第一步是对于每个元素 以它为最小值的最大区间是什么
第二步是找出来在这个区间里面 最大的连续和多少
那么我们怎么找到第一步这个最大区间呢
可以先找这个元素左边第一个比他小的值的下标 和右边第一个比他小的值的下标 这两个下标确定了 最大区间就确定了
怎么找这个下标呢 暴力的话时间复杂度太高 是n^2 需要使用单调栈：
单调栈 顾名思义就是元素都是单调递增或者递减的栈 至于它有什么作用 接着往下看
假如有一个数组a: 3 5 1 6 2
用数组 L 表示a数组里的每一个元素 从自身位置 向左 第一个比它小的元素的位置
那么L就应该是： 0 1 0 3 3 （这里为了方便表示 我让a数组的下标从1开始标记 这样L数组里面 0 就表示左边的数都比他大 1 就表示第一个数比他小 以此类推）
那么我们怎么利用单调栈实现呢？
先将 a[0]赋值为一个极小值 -0x7ffffff，然后将0入栈
对于数组a的每一个元素 进行如下语句：
while(a[S.top()]>=a[i])
S.pop();
l[i] = S.top();
S.push(i);
while语句 保证了栈里面的数据是单调递减的
看不明白没有关系 让我们模拟一下：
i==1时 a[S.top]=a[0]=-0x7ffffff 不进入while循环
所以L[1]=0；
将1入栈 此时的栈：0 1（实际上我们比较的是a[i] 所以逻辑上来讲 此时的栈：a[0] a[1] 也就是 -0x7ffff 3 因为我们需要用到左边的下标值 所以是将下标入栈 这样既可以访问到下标所对应的值 也可以访问下标）
i==2时，a[S.top]=a[1]=3 小于5 还是不进入while循环
L[2]=S.top()=1
将2入栈 此时的栈：0 1 2（-0x7ffff 3 5 ）
i==3时，a[S.top]=a[2]=5 大于1
S.pop()，a[S.top]=a[1]=3还是大于1
S.pop()，a[S.top]=a[0]=-0x7ffffff 小于1 结束循环
所以L[3]=0
将3入栈 此时的栈：0 3（-0x7ffff 1）
.........
以此类推
逻辑上栈中的元素（a[i]）始终是递减的
这样我们就通过以此循环求出了L数组 也就是找到了之前说的 最大区间的左边界 找右边界也是一样的思路，只是循环的方向不同
好了现在我们完成了第一步 要进行第二步 也就是找每个区间里面的最大连续和（如果a[i]<0的话需要找最小连续和）
如果a[i]均为非负的话就很简单了 肯定是区间越长 连续和越大 但问题是a[i]是可以有负数的
那就需要分情况讨论了
我们可以开4个数组 lmax lmin rmax rmin
lmax 和 rmax 用来记录最大连续和的区间的左右下标
lmin 和 rmin 记录最小的和的左右下标
怎么更新这四个数组呢？
for(i=;i<=n;i++)
{
if(s[i-]-s[lmin[i-]-]>)
lmin[i]=i;
else
lmin[i]=lmin[i-];
if(s[i-]-s[lmax[i-]-]<)
lmax[i]=i;
else
lmax[i]=lmax[i-];
}
s[i]是前i项的和
看代码很容易理解 如果前面几项的和是正的 那就不要他 让lmin[i]=i 如果是负的 那么加上他 这样连续和就会变小
rmax和rmin只需要倒着更新就行
最后别忘了 这四个数组必须是在L数组和R数组的范围内的 相当于第一步是第二步的限制条件：
if(a[i]<)
{
ll=max(l[i]+,lmin[i]);
rr=min(r[i]-,rmin[i]);
}
else
{
ll=max(l[i]+,lmax[i]);
rr=min(r[i]-,rmax[i]);
}
完整ac代码：
#include<bits/stdc++.h> using namespace std; long long i,n,ll,rr,s[],a[],lmin[],lmax[],rmin[],rmax[],l[],r[],ans;
stack<long long> S; int main()
{
cin>>n;
for(i=;i<=n;i++)
{
cin>>a[i];
s[i]=s[i-]+a[i];
}
ans=a[]*a[];
S.push();
a[]=-0x7fffff;
a[n+]=-0x7fffff-;
for(i=;i<=n;i++)
{
while(a[S.top()]>=a[i])
S.pop();
l[i] = S.top();
S.push(i);
}
while(S.size())
S.pop();
S.push(n+);
for(i=n;i>=;i--)
{
while(a[S.top()]>=a[i])
S.pop();
r[i]=S.top();
S.push(i);
}
lmin[]=;
lmax[]=;
rmin[n]=n;
rmax[n]=n;
for(i=;i<=n;i++)
{
if(s[i-]-s[lmin[i-]-]>)
lmin[i]=i;
else
lmin[i]=lmin[i-];
if(s[i-]-s[lmax[i-]-]<)
lmax[i]=i;
else
lmax[i]=lmax[i-];
}
for(i=n-;i>=;i--)
{
if(s[rmin[i+]]-s[i]>)
rmin[i]=i;
else
rmin[i]=rmin[i+];
if(s[rmax[i+]]-s[i]<)
rmax[i]=i;
else
rmax[i]=rmax[i+];
}
for(i=;i<=n;i++)
{
if(a[i]<)
{
ll=max(l[i]+,lmin[i]);
rr=min(r[i]-,rmin[i]);
}
else
{
ll=max(l[i]+,lmax[i]);
rr=min(r[i]-,rmax[i]);
}
ans=max(ans,a[i]*(s[rr]-s[ll-]));
}
cout<<ans; }