b_zj_选区间（单调栈+撩脑）

求区间中的最小数*区间所有数的和的最大值

思路：单调递增栈，每次遇到一个比栈顶更小的元素，就需要让栈顶作为区间的最小值和ans比较（防止丢失），此时的区间还不能取到第i个位置

#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7, N=1e6+5;
int A[N], s[N];
int main() {
    std::ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int n, ans = INT_MIN; cin>>n;
    stack<int> st;
    for (int i=1; i<=n; i++) {
        cin>>A[i]; s[i] = s[i-1] + A[i];
    }
    for (int i=1; i<=n; i++) {
        while (!st.empty() && A[i] <= A[st.top()]) {
            int cur_min = A[st.top()]; st.pop();
            int l = 0;
            if (!st.empty()) l = st.top();
            ans = max(ans, cur_min * (s[i-1] - s[l]));
        }
        st.push(i);
    }//还没处理完的情况
    while (!st.empty()) {
        int cur_min = A[st.top()]; st.pop();
        int l = 0;
        if (!st.empty()) l = st.top();
        ans = max(ans, cur_min * (s[n] - s[l]));
    }
    cout << ans;
    return 0;
}

b_zj_选区间（单调栈+撩脑）

原文：https://www.cnblogs.com/wdt1/p/14495428.html