C++ 解法, 执行用时: 30ms, 内存消耗: 5200KB, 提交时间: 2021-03-08

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pii;
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;
}

C++ 解法, 执行用时: 31ms, 内存消耗: 1668KB, 提交时间: 2021-06-28

#include <bits/stdc++.h>
using namespace std;
struct param{
    int value;//这个储存节点值
    int accumu;//这个储存在单调栈中的比它大的值的和
}data;
int main(int argc,char** argv){
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int n;
    cin>>n;
    stack<param>s;//单调栈，一直对其进行维护使其保持递增状态
    int maxval=0,tmp=0;
    for(int i=0;i<n;i++){
        cin>>data.value;
        data.accumu=data.value;
        if(i!=0&&data.value<=s.top().value){
            tmp=0;
            while(!s.empty()&&data.value<=s.top().value){
                tmp=tmp+s.top().accumu;
                maxval=max(maxval,tmp*s.top().value);
                s.pop();
            }
            data.accumu=data.accumu+tmp;
        }
        s.push(data);
    }
    tmp=0;
    while(!s.empty()){
        tmp=tmp+s.top().accumu;
        maxval=max(maxval,tmp*s.top().value);
        s.pop();
    }
    cout<<maxval<<endl;
}