既然所有数都是大于等于0的，那么在一个区间最小值一定的情况下，这个区间越长越好（当然有特殊情况）对一个数a[i],left[i]代表左边第一个比它小的,right[i]代表右边第一个比它小的如何构造left[i]呢？，，从左往右构造一个单调递增的栈（一定是单调的！）当a[i]比栈顶元素小的时候，栈顶元素出栈，（否则的话入栈，left[i]就是栈顶元素的位置，right数组同理可得注意2个方面一个是栈空的时候的讨论，另外一个，如果写出来WA的话，试一下这组数据：60 0 0 0 0 0结果应该是01 1而不是0
1 6
#include<cstdio>#include<queue>#include<stack>#include<cstring>#include<algorithm>using namespace std;typedef long long LL;const int maxn = 100005;int n;stack<int>s;LL arr[maxn];int left[maxn],right[maxn];LL sum[maxn];void solve1(){while(!s.empty()) s.pop();for(int i = 1; i <= n; i++){LL e = arr[i];do{if(s.empty()){left[i] = 0;s.push(i);break;}LL c = arr[s.top()];if(c < e){left[i] = s.top();s.push(i);break;}else s.pop();}while(true);}}void solve2(){while(!s.empty()) s.pop();for(int i = n; i >= 1; i–){LL e = arr[i];do{if(s.empty()){right[i] = n + 1;s.push(i);break;}LL c = arr[s.top()];if(c < e){right[i] = s.top();s.push(i);break;}else s.pop();}while(true);}}int main(){int Case = 0;while(scanf("%d",&n) != EOF){sum[0] = 0L;for(int i = 1; i <= n; i++){scanf("%lld",&arr[i]);sum[i] = sum[i – 1] + arr[i];}solve1();solve2();LL ans = -1;int pos_x,pos_y;int l;for(int i = 1; i <= n; i++){int a = left[i];int b = right[i];int ll = (b – 1) – (a + 1);LL max_sum = (sum[b – 1] – sum[a]) * arr[i];if(max_sum > ans){pos_x = a + 1;pos_y = b – 1;l = pos_y – pos_x;ans = max_sum;}else if(max_sum == ans && ll < l){pos_x = a + 1;pos_y = b – 1;l = pos_y – pos_x;}}if(Case++) puts("");printf("%lld\n",ans);if(ans == 0)printf("%d %d\n",pos_x,pos_x);elseprintf("%d %d\n",pos_x,pos_y);}return 0;}
不要做刺猬能不与人结仇就不与人结仇，
