题意：给定一个序列，需要找出某个子序列S使得Min(a[i])*Σa[i] (i属于S序列)最大
正解：单调栈
这题的暴力还是很好想的，只需3分钟的事就可以码完，以每个点拓展即可，但这样的复杂度是O（n^2）的，肯定会TLE
以暴力的思想作为基础，再进行深层次思考，考虑每个点往周围拓展的时候，都要走到最远的地方停下来，也就是说会有一个左上限，一个右上限（命名为：pre、next），不难发现再枚举5、4、3、2、1这个序列的时候，每次都要往左扫描到最左边，显然这是做了重复的事情，于是机智的我马上想到了单调栈。为什么说具有单调性呢，因为x<y,对于x可以控制的所有范围显然y都可以控制，这不是废话吗。于是我们想到了用单调栈来解决这个问题。
什么是单调栈呢，单调栈分为单调增栈和单调减栈两种。比如说：单调增栈就是以某一个值为最小值，然后维护一个单调递增的序列。将一元素加入栈时，先判断它是否大于栈顶元素，若是大于栈顶元素，加入栈。否则，将栈顶元素出栈，直到栈顶元素小于要加入栈的元素。
对于这道题而言，我们不妨维护每个端点能够往前往后拓展的最大值，在删除栈顶元素的时候“继承”此时栈顶的范围就可以了（上面提到的单调性）
呼，这样的话这道单调栈裸题就可以AC了。记得开long long。第一次提交又没开long long然后WA了
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<cmath> 5 #include<cstdlib> 6 #include<algorithm> 7 #include<queue> 8 #include<map> 9 #include<vector> 10 #include<stack> 11 using namespace std; 12 typedef long long LL; 13 const int MAXN = 110011; 14 int n; 15 LL a[MAXN]; 16 LL ans,now; 17 LL qian[MAXN]; 18 int nowl,nowr; 19 20 struct node{ 21 int jilu; 22 int pre,next; 23 LL num; 24 }; 25 26 stack<node>Stack; 27 28 inline LL getlong(){ 29 char c=getchar();LL w=0;int q=0; 30 while( (c<'0' || c>'9') && c!='-' ) c=getchar(); 31 if(c=='-') c=getchar(),q=1; 32 while(c<='9' && c>='0') w=w*10+c-'0',c=getchar(); 33 return q?-w:w; 34 } 35 36 inline void Init(){ 37 scanf("%d",&n); 38 ans=now=-1; nowl=nowr=0; qian[0]=0; 39 for(int i=1;i<=n;i++) a[i]=getlong(),qian[i]=qian[i-1]+a[i]; 40 while(!Stack.empty()) Stack.pop(); 41 } 42 43 inline void work(){ 44 node jump; 45 46 jump.num=a[1]; 47 jump.pre=jump.next=1; 48 jump.jilu=1; 49 Stack.push(jump); 50 51 node ljh; 52 for(int i=2;i<=n;i++) { 53 ljh.num=a[i]; 54 ljh.pre=ljh.next=1; 55 ljh.jilu=i; 56 57 while(!Stack.empty() && a[i]<=Stack.top().num) { 58 jump=Stack.top(); 59 Stack.pop(); 60 if(!Stack.empty()) Stack.top().next+=jump.next; 61 ljh.pre+=jump.pre; 62 63 now=jump.num*(qian[ jump.jilu+jump.next-1 ]-qian[ jump.jilu-jump.pre ]); 64 65 if(now>ans) { 66 ans=now; 67 nowl=jump.jilu-jump.pre+1; nowr=jump.jilu+jump.next-1; 68 } 69 } 70 71 Stack.push(ljh); 72 } 73 74 while(!Stack.empty()) { 75 jump=Stack.top(); 76 Stack.pop(); 77 78 if(!Stack.empty()) Stack.top().next+=jump.next; 79 80 now=jump.num*(qian[ jump.jilu+jump.next-1 ]-qian[ jump.jilu-jump.pre ]); 81 if(now>ans) { 82 ans=now; 83 nowl=jump.jilu-jump.pre+1; nowr=jump.jilu+jump.next-1; 84 } 85 } 86 87 if(n==0) ans=0; 88 printf("%lld %d %d ",ans,nowl,nowr); 89 } 90 91 int main() 92 { 93 freopen("poj2796.in","r",stdin); 94 freopen("poj2796.out","w",stdout); 95 96 Init(); 97 98 work(); 99 return 0; 100 }