UVa 1619 感觉不错（Feel Good）

题意：
找到一个连续的子序列 令 e = 这段连续子序列的和 * 这段连续子序列中的最小值， 求令e最大的区间和e的值

分析：
可以考虑用单调递增栈做，同时注意用LL
用单调递增栈的算法复杂度为O（n）

代码：

#include<bits/stdc++.h>
#define LL long long
#define ms(s) memset(s, 0, sizeof(s))
using namespace std;
const int maxn = 1e5 + 10;
LL a[maxn];
LL sum[maxn];

//题目有误，当最大值相同时不是输出任意区间都可以的
//应该是输出最短的区间，长度相同时输出左端点最小的区间

int main() {
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    int kase = 0;
    while(cin >> n && n) {
        if(kase++) std::cout << endl;
        sum[0] = 0;
        for(int i = 1; i <= n; i++) {
            cin >> a[i];
            sum[i] = a[i] + sum[i - 1];
        }
        a[n + 1] = -1;
        stack<LL> s;
        LL maxd = -1;
        int i = 1;
        int l = 1, r = n + 1;
        while(i <= n + 1) {
            if(s.empty() || a[s.top()] < a[i]) {
                s.push(i++);
            } else {
                int t = s.top();
                s.pop();
                LL e;
                if(s.empty()) {
                    e = a[t] * sum[i - 1];
                    if(e > maxd) {
                        l = 1;
                        r = i - 1;
                        maxd = e;
                    }
                } else {
                    e = a[t] * (sum[i - 1] - sum[s.top()]);
                    if(e > maxd ||
                    ((e == maxd) && (i - 2 - s.top() < r - l))) {
                        l = s.top() + 1;
                        r = i - 1;
                        maxd = e;
                    }
                }

            }
        }
        std::cout << maxd << endl;
        std::cout << l << " " << r << endl;
    }

    return 0;
}

证明：

如果样例是 2 1 5 6 2 3
在这种情况下 如果栈为空就将元素入栈
这个时候2入栈了
然后因为遇到1，有1的情况下2就不可能作为最小值，因此2出栈，这个时候把2当作最小值， 2 * 2 = 4
之后1入栈 接下来由于 5 大于1 6大于5 因此都入栈
这个时候2入栈了 在有2的情况下 6不可能作为最小值，因此6出栈，由于是单调递增栈，因此6左边的那个数，也就是去除6后的栈头，比6来的小，因此左边也不可能作为最小值，因此就是这个元素6到此时把6出栈后栈顶的位置，在这个区间内，6可以作为最小值。
这里注意如果出栈后栈为空，说明这个元素是当前序列中所有元素的最小值。

由于每个元素都只入栈一次，出栈一次，因此时间复杂度为O（n）
由于每个元素都作为最小值被出栈，因此该算法是正确的
由于需要出栈，才可以作为最小值，因此最右边填充a[n + 1] = - 1 保证所有元素均出栈。