題干：

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? Feel Good

Time Limit:?3000MS	?	Memory Limit:?65536K
Total Submissions:?12409	?	Accepted:?3484
Case Time Limit:?1000MS	?	Special Judge

Description

Bill is developing a new mathematical theory for human emotions. His recent investigations are dedicated to studying how good or bad days influent people's memories about some period of life.?

A new idea Bill has recently developed assigns a non-negative integer value to each day of human life.?

Bill calls this value the emotional value of the day. The greater the emotional value is, the better the daywas. Bill suggests that the value of some period of human life is proportional to the sum of the emotional values of the days in the given period, multiplied by the smallest emotional value of the day in it. This schema reflects that good on average period can be greatly spoiled by one very bad day.?

Now Bill is planning to investigate his own life and find the period of his life that had the greatest value. Help him to do so.

Input

The first line of the input contains n - the number of days of Bill's life he is planning to investigate(1 <= n <= 100 000). The rest of the file contains n integer numbers a1, a2, ... an ranging from 0 to 10?6?- the emotional values of the days. Numbers are separated by spaces and/or line breaks.

Output

Print the greatest value of some period of Bill's life in the first line. And on the second line print two numbers l and r such that the period from l-th to r-th day of Bill's life(inclusive) has the greatest possible value. If there are multiple periods with the greatest possible value,then print any one of them.

Sample Input

6 3 1 6 4 5 2

Sample Output

60 3 5

解題報告：

? ? ?這個題干是真，的，惡，心。一會最大一會最小，搞這么復雜弄的題目看半天。。不過抽出核心部分就是一句話，求一個給定區間的 ? ?區間和與該區間最小值的 ?最大值。這題與HDU-1506那道Largest Rectangle（求最大矩形面積）差不多。

那道題的思路是：反正得是個矩形 還需要最大面積，那上底邊一定和某一個高度相等吧？那我就把每個高度所能延伸到的最遠距離（也就是矩形的長）求出來，最后"長"乘"高"，里面肯定有我要的答案了啊。而求每一個高度對應的"長"的過程，也就是單調棧的過程。

本題也是一樣，我就把每一個a[i] 都當做最小值，左邊右邊分別看看最遠能延伸哪（這一步用單調棧），然后乘起來放在maxx里，維護maxx不就好了嗎。

? ?另一個題解中的解釋我覺得不錯：

題意是給出一個序列，要求的是一個區間，這個區間的最小值乘以這個區間數字的和 是最大值。求這個最大值與這個區間。

即：給你n個數，求一個?max，其中max=某個區間和*該區間的最小值。

ac代碼1：

#include<iostream> #include<cstdio> #include<algorithm> #include<stack> using namespace std;const int MAX = 1e6 + 5; int a[MAX], L[MAX], R[MAX], top; long long sum[MAX]; int n; int l,r; long long maxx; stack<int > sk; int main() {cin>>n;for(int i = 1; i<=n; i++) {scanf("%d",&a[i]);sum[i] = sum[i-1] + a[i];}//需要左側第一個比a[i]小的元素，所以 從左向右維護一個嚴格單調遞增棧 for(int i = 1; i<=n; i++) {while(!sk.empty() && a[sk.top() ] >= a[i]) sk.pop();if(sk.empty() ) L[i] = 0;else L[i] = sk.top();sk.push(i);}while(!sk.empty() ) sk.pop();//需要右側第一個比a[i]小的元素，所以 從右向左維護一個嚴格單調遞增棧 for(int i = n; i>=1; i--) {while(!sk.empty() && a[sk.top() ] >= a[i]) sk.pop();if(sk.empty() ) R[i] = n+1;else R[i] = sk.top();sk.push(i);}l=r=1;long long tmp;for(int i = 1; i<=n; i++) {tmp=sum[R[i] - 1 ] - sum[L[i] ];tmp*=a[i];if(tmp>maxx) {l=L[i]+1;r=R[i]-1;maxx=tmp;} } // printf("%d %d\n",L[4],R[4]);printf("%lld\n",maxx);printf("%d %d\n",l,r);return 0 ;}

初始化的細節！！！！！

注意上面這個代碼中，末尾的l=r=1是有講頭的，此處賦值成別的值就wa了。原因如下：（感謝wjh巨巨的分享）

? ? ?要么maxx賦初始值-1 ? 要么寫tmp>=maxx （這兩種情況的l和r都不需要賦初始值）。

? ? ?如果你按ac代碼中這樣寫，那就只能l=r=1才可以！！ 因為這題卡了極限樣例需要特判一下：這樣輸入：1\n0\n ?或者1\n3\n你會發現輸出都是你賦值的l

---

別的ac代碼：（維護單調遞減棧？也可以做？）（好像還是遞增棧、、、）

實際上這個題目就是要對每一個節點進行擴展，這樣擴展的話，復雜度是O(n^2)。減少時間復雜度要用單調棧，單調棧處理的問題就是對每一個節點進行擴展的問題，這個題目要維護的是一個單調遞減棧，即從棧頂元素到棧底元素，值是單調遞減的，即棧頂元素的值始終是棧的最大值。然后每一個值有屬于自己的區間，這個區間目的是為了記錄之后的元素向前延伸的用處。

向后延伸就靠從1到n掃描元素，(維護單調遞減棧)這樣當掃描的元素大于棧頂元素時，直接入棧。

當掃描的元素等于棧頂元素時，不記錄，只將區間延伸到后面。

當掃描的元素小于棧頂元素時，這時要計算棧內當前的值。因為掃描的元素時小于棧頂元素的，要求的是一個區間的最小值，所以棧內那些大于該元素的值你會發現沒有用處了，只需要將它們的那些區間留下來就對了，這就是向前擴展。

拿題目的sample舉例子：

3 1 6 4 5 2

?

一開始每一個數都有自己的區間：

3(1,1) ?1(2,2) ?6(3,3) ?4(4,4) ?5(5,5) ?2(6,6) ?-1(7,7)后面加一個最小值，為了最后計算棧內元素使用。

先是3入棧。棧內元素 3(1,1)

1<3，首先計算一下棧內元素的值，記錄下來。然后要把棧內大于1的全部彈出來，但是把它們的區間留下，棧內就變成了1(1,2)。實際上此時就會知道(1,2)這段區間之內的最小值是1。

6>1，直接入棧，棧內元素變為1(1,2)，6(3,3)。

4<6，將6彈出，彈出之前計算值。然后棧內就變為1(1,2)，4(3,4)。

5>4，直接入棧。棧內元素是1(1,2),4(3,4),5(5,5)。會發現因為5沒有辦法向前擴展了所以會知道5只能夠在(5,5)的區間內最小，所以說站內元素是在自己區間的左端點與棧頂元素的右端點，這段區間之內滿足著最小值的關系。1是在(1,5)這段區間內最小，4是在(3,5)這段區間內最小。這些值都會在碰到掃描的元素小于該元素時計算，記錄下來，就是這樣單調棧完成了對每一個元素進行左右擴展的目的。

2<5,2<4。要把5(5,5) 4(3,4)分別彈出，它們走之前要計算各自區間的值。

最后是-1，目的就是要將棧內所有元素彈出，計算每一個元素左右擴展的值。

#include <functional> #include <algorithm> #include <iostream> #include <fstream> #include <cstring> #include <cstdio> #include <cmath> #include <cstdlib> #include <queue> #include <stack> #include <map> #include <bitset> #include <set> #include <vector>using namespace std;const double pi = acos(-1.0); const int inf = 0x3f3f3f3f; const double eps = 1e-15; typedef long long LL; typedef pair <int, int> PLL;static const int N = 100100; stack <PLL> st; int val[N]; LL sum[N]; int l[N]; int r[N];int main() {int n;while (~scanf("%d", &n)) {sum[0] = 0;for (int i = 1; i <= n; ++i) {scanf("%d", &val[i]);sum[i] = sum[i - 1] + val[i];l[i] = r[i] = i;}while (!st.empty()) {st.pop();}for (int i = n; i >= 1; --i) {if (st.empty()) {st.push(make_pair(val[i], i));}else {while (!st.empty()) {PLL u = st.top();if (val[i] >= u.first) {break;}st.pop();l[u.second] = i + 1;}st.push(make_pair(val[i], i));}}while (!st.empty()) {PLL u = st.top();st.pop();l[u.second] = 1;}for (int i = 1; i <= n; ++i) {if (st.empty()) {st.push(make_pair(val[i], i));}else {while (!st.empty()) {PLL u = st.top();if (val[i] >= u.first) {break;}st.pop();r[u.second] = i - 1;}st.push(make_pair(val[i], i));}}while (!st.empty()) {PLL u = st.top();st.pop();r[u.second] = n;}LL ans = -1;int L, R;for (int i = 1; i <= n; ++i) {int y = r[i];int x = l[i];if (ans < (sum[y] - sum[x - 1]) * val[i]) {ans = (sum[y] - sum[x - 1]) * val[i];L = x;R = y;}}printf("%lld\n", ans);printf("%d %d\n", L, R);}return 0; }

總結：

? ? 至今不明白為什么要維護一個嚴格單調遞增棧。?

? ?答：因為你要的是一個嚴格小于你的元素，然后要取這兩個下標中間的區域作為區間（因為中間就都是比你大的或相等的了）。所以，其實使用單調遞增棧（以此舉例）的目的不是為了找第一個嚴格比你小的值（雖然具體實現是這樣的）而是為了找中間那部分都比你大的值的所在區間。嚴格單調遞增棧（實現語句為帶等號的 a[sk.top() ] >= a[i] ? -> ?then pop掉），找通過找嚴格小于他的第一個元素，目的是尋求大于等于他的那部分區間區域。這幾個邏輯關系要搞清楚！！

（但有的題 ? 用單調遞減棧目的就是很單純的找第一個比他高的元素，eg HDU 5033）稍后貼博客

與滑窗算法做區別？

滑動窗口的精髓是在一個數列里保存著一個遞增數列，同時這個數列維持了它在原數列的位次遞增，這個窗口里保存的第一個數即在這個區間里最小的數。這樣不停得把新輸入的數同這個滑動窗口里右邊的數比較，如果比它大，刪除窗口里的這個數，同時刪除的數統治區域的最右邊就是新輸入的數，它的左統治區域即新輸入的數的左統治區域，然后不停地向窗口的左邊比。這樣只需要一個數組記錄它左邊區域的邊界就可以了，? 右邊同理..

附一個滑窗算法典型題目 ? ??【POJ - 2823】 Sliding Window

題解：https://blog.csdn.net/qq_41289920/article/details/81071905

總結

以上是生活随笔為你收集整理的*【POJ - 2796】 Feel Good （前缀和优化+单调栈维护）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。