该题我跑了0.251s，名列第三。。第一第二比我这个优化了好多，真不知道怎么弄的 ，感觉已经无法优化了 。 该题的关键是求出一个数作为最小值的最大区间，看到网上很多人都是向两边扫的方法，说实话我觉得在如果数据极端一点，这个方法是很“危险的”。 我认为该题的正解是紫书上P241页所讲的内容，即维护一个单调队列，动态维护求出每个数以它为最小值的最大区间 。因为每个数只插入和删除一次，所以 只需要O（n）的复杂度 。 怎么样？很神奇吧 ！   该题的难点就在于求区间最小值， 所以这个方法再适合不过了 。下面我将详细讲解一下： 说起来也简单，大家可以出一组数据，按我的说法演算一遍，就可以更加深刻的体会这种思想了 。 就是用一个数组，通过一个指针rear来维护这个数组，使得这个数组里的数单调上升，即维护一个单调队列 。 然后每加进去一个数j，就向前检查比他大的数，假设检查了i，它比新加进来的数大，那么就删除它（rear--），并且这个被删除的数的右区间就是j-1 ，然后j的左区间变成了被删除的这个数的左区间，然后继续上述过程，直到没有大于j的数 ，将j加入队列就可以了 。至于为什么这样是对的，如果理解了我说的过程是很容易明白的，那些被删除的数比新加进来的数大，所以这些数的左区间，肯定也包括在新加进来的数的区间之中 。 然后最后这个队列中还可能留下一些数，那么这些数的右区间就都是n了 。 细节参见代码： ~~~ #include<bits/stdc++.h> using namespace std; const int maxn = 100000 + 5; int n,a[maxn],l[maxn],r[maxn],flage=0; long long sum[maxn]; struct point { int v,x; }cur[maxn]; int main() { while(~scanf("%d",&n)){ for(int i=1;i<=n;i++) { scanf("%d",&a[i]); sum[i] = sum[i-1] + a[i]; } int rear = 1; cur[0].v = -1; for(int i=1;i<=n;i++) { l[i] = i; //初始化左边界 while(rear>=1 && cur[rear-1].v >= a[i]) { //删除队列中比a[i]大的数 rear--; r[cur[rear].x] = i-1; //确定右边界 l[i] = l[cur[rear].x]; //更新左边界 } cur[rear].x = i; cur[rear++].v = a[i]; //加入新值 } for(int i=1;i<rear;i++) //确定队列中剩下的数的右边界 r[cur[i].x] = n; long long ans = -1; int len,ans_l,ans_r; for(int i=1;i<=n;i++) {//求最优解和对应区间 int L = l[i],R = r[i]; long long v = (sum[R] - sum[L-1])*a[i]; if(ans < v || (ans == v && len > R-L)) { ans = v; ans_l = L; ans_r = R; len = R-L; } } if(flage) printf("\n"); else flage = 1; printf("%lld\n%d %d\n",ans,ans_l,ans_r); } return 0; } ~~~