一、题意

给出一个长度为n（n<=100000）的正整数序列ai，求出一段连续子序列a[l..r]使得 （al+...+ar）*min{al,...,ar}尽量大。
输出最大值和对应的区间。当区间相同时，输出最短的区间，长度相同时输出左端点最小的区间。

二、解析

区间和是很容易得到的，通过预先算好一个sum[maxn]数组即可。
重点是如何快速得到一个区间的最小值。

这里的方法是反向思考，即将原问题改为：如何在确定一个数作为最小值后，得到它的最大区间？
即我们把a[i]作为最小值时，需要得到包含它的区间的左右边界l[i]、r[i]。

而获取左边界和右边界是镜像问题，因此我们不妨考虑如何获取左边界。

实际上获取左边界可以通过单调栈来实现。栈中存放下标。
维护一个单调递增的栈，每遍历到一个a[i]时，先通过while循环把栈顶中大于（或等于）a[i]的元素全部弹出，以保证栈中的值保持单调递增。此时剩余的栈顶元素+1即为以a[i]为最小值的区间的左端点下标（因为该栈顶元素所对应的值是a[i]向左第一个比它小的值，中间的值都由于比它大或相等而被弹出了）；若此时没有栈顶元素，说明左侧没有元素比a[i]小，因此令l[i]:=0。然后再把a[i]压入栈中，它可能会成为后面元素的左边界。
这样就能得到l[i]数组了，r[i]数组只需要镜像处理就可以得到。
最终再通过遍历一下下标然后比对出最大值即可。

PS: 这道题注意全零这一个特例, 搞得我wa了好多次...

三、代码

#include <iostream>
#include <stack>
#define mp make_pair
using namespace std;
using LL = long long;
const int maxn = 100000 + 5;
int n, a[maxn], l[maxn], r[maxn];
LL sum[maxn];
bool first = 1;

int main() {
    while(cin >> n) {
        sum[0] = 0;
        for(int i = 0; i < n; i ++) cin >> a[i], sum[i + 1] = sum[i] + a[i];

        stack<int> stk_l, stk_r;
        for(int i = 0; i < n; i ++) {
            while(!stk_l.empty() && (a[stk_l.top()] > a[i] || (a[i] && a[stk_l.top()] == a[i]))) stk_l.pop();
            l[i] = (stk_l.empty() ? 0 : (stk_l.top() + 1));
            stk_l.push(i);
        }
        for(int i = n - 1; i >= 0; i --) {
            while(!stk_r.empty() && (a[stk_r.top()] > a[i] || (a[i] && a[stk_r.top()] == a[i]))) stk_r.pop();
            r[i] = (stk_r.empty() ? (n - 1) : (stk_r.top() - 1));
            stk_r.push(i);
        }

        LL ans = -1;
        int idx = 0;
        for(int i = 0; i < n; i ++) {
            LL val = (sum[r[i] + 1] - sum[l[i]]) * a[i];
            if(mp(ans, mp(-r[idx] + l[idx], -l[idx])) < mp(val, mp(-r[i] + l[i], -l[i]))) ans = val, idx = i;
        }
        if(first) first = 0;
        else cout << endl;
        cout << ans << "\n" << l[idx] + 1 << " " << r[idx] + 1 << endl;
    }
}

四、归纳

  • 单调栈：即保持栈内元素的单调性，存放下标还是值可以依情况而定。由于每个元素最多弹出一次，因此单调栈算法是O(n)的。
  • 单调栈在本题中的作用：得到到当前元素为止的单调递增序列，从而能得到离自己最近的比自己小的元素。只有 [比自己大的元素]， 或者 [比自己小但是却被离得更近的更小的元素弹走的元素] 才不会出现在栈中。