該題我跑了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; } ~~~