题目来源

POJ2796 FeelGood

http://poj.org/problem?id=2796

洛谷P2422 良好的感觉

https://www.luogu.org/problem/show?pid=2422

思路

设置一个结构体（k{long long num,pos;}) 存数值大小和这个数在原序列中的编号

设置一个数组pre[i]记录前缀和

正反各做一遍O(n)的单调递增的单调栈 计算以当前数a[i]为最小值的区间可以延伸到最前位置fr[i]+1和最后位置ba[i]-1

最后用O(n)计算每个数对应的最大（最小值*区间和）统计答案

代码

#include <cstdio> #include <stack> using namespace std; long long n,a[100010],pre[100010],ans=-1; long long fr[100010],ba[100010],l,r; struct k{long long num,pos;}; stack <k> f,b; int main() { scanf("%lld",&n); for(long long i=1;i<=n;++i) scanf("%lld",&a[i]),pre[i]=pre[i-1]+a[i]; f.push((k){-1,0}); for(long long i=1;i<=n;++i) { while(!f.empty()&&f.top().num>=a[i]) f.pop(); fr[i]=f.top().pos; f.push((k){a[i],i}); } b.push((k){-1,n+1}); for(long long i=n;i>=1;--i) { while(!b.empty()&&b.top().num>=a[i]) b.pop(); ba[i]=b.top().pos; b.push((k){a[i],i}); } for(long long i=1;i<=n;++i) { if((long long)a[i]*(pre[ba[i]-1]-pre[fr[i]])>ans) { ans=(long long)a[i]*(pre[ba[i]-1]-pre[fr[i]]); l=fr[i]+1; r=ba[i]-1; } } printf("%lld\n%lld %lld",ans,l,r); return 0; }