poj 2796 Feel Good(单调栈)
题目链接：poj 2796 Feel Good
题意：
给你n个数，定义一个区间的值为这个区间的最小值乘上这个区间的数的和。
让你选一个值最大的区间。
题解：
考虑以每一个数作为区间的最小值，那么现在问题就转换成了如果以这个数为最小值，那么从这个位置开始左右最远能到哪个位置。
这里就要用到单调栈了。维护一个单调递减的栈，栈顶就是当前的最小值。
然后从左往右扫一遍，从右往左扫一遍就行了。
如果不懂原理的话，网上搜搜这题的其他题解，比我讲的详细。(懒)
1 #include<cstdio> 2 #include<algorithm> 3 #define F(i,a,b) for(int i=(a);i<=(b);++i) 4 using namespace std; 5 typedef long long ll; 6 7 const int N=1e5+7; 8 int n,a[N],l[N],r[N],S[N],top; 9 ll sum[N]; 10 int main() 11 { 12 while(~scanf("%d",&n)) 13 { 14 F(i,1,n)scanf("%d",a+i),sum[i]=sum[i-1]+a[i]; 15 top=0; 16 F(i,1,n) 17 { 18 l[i]=i; 19 while(top&&a[i]<=a[S[top]])l[i]=l[S[top]],top--; 20 S[++top]=i; 21 } 22 top=0; 23 for(int i=n;i>=1;i--) 24 { 25 r[i]=i; 26 while(top&&a[i]<=a[S[top]])r[i]=r[S[top]],top--; 27 S[++top]=i; 28 } 29 ll ans=-1;int L,R; 30 F(i,1,n) 31 { 32 ll tmp=(sum[r[i]]-sum[l[i]-1])*a[i]; 33 if(tmp>ans)ans=tmp,L=l[i],R=r[i]; 34 } 35 printf("%lld %d %d ",ans,L,R); 36 } 37 return 0; 38 }