考点:前缀和 和 单调栈

举例：[6,2,1,3]

选择第一个数 6，以 6 为最小值的区间是 [6], 结果是 6 * 6 = 36

选择第二个数 2，以 2 为最小值的区间是 [6，2], 结果是 ( 6 + 2 ) * 2 = 24

选择第三个数 1，以 1 为最小值的区间是 [6, 2, 1, 3], 结果是 ( 6 + 2 + 3 + 1) * 1 = 12

选择第四个数 3，以 3 为最小值的区间是 [3], 结果是 3 * 3 = 9

答案是 36

解题思路：枚举各个数字，求出以枚举到的数字为最小值的区间的计算结果，保存最大的结果输出。

例如求以第三个数 1 为最小值的区间，需要找到 1 左侧 第一个比 1 小的数字，以及 1 右侧第一个比 1 小的数。

如果使用暴力枚举，时间复杂度是过高，超时。因此需要如下优化：

找出某个数字一侧比它小的第一个数字---》使用单调栈

找到区间后，求出区间内所有数字的和---》求某个区间的数字和，使用前缀和。

时间复杂度：

单调栈找某个区间的边界：O(n)

前缀和求区间和：O(n)

加法原理：总时间复杂度 O(n)。

数据范围：50w, 不会超时。

#include<algorithm>
#include<stack>
using namespace std;
typedef long long LL;
const int N = 500010;
int a[N];
int s[N];
int n;
stack<int> st;
int main(){
    cin >> n;
    for(int i = 1; i <= n; i++){
        scanf("%d", a + i);
        s[i] = s[i - 1] + a[i];
    }
    a[n + 1] = -1;
    LL res = 0;
    for(int i = 1; i <= n; i++){
        while(st.size() && a[i] <= a[st.top()]){
            int k = st.top();
            st.pop();
            int r = i;
            int l = 0;
            if(st.size()) l = st.top();
            res = res > (s[r - 1] - s[l]) * a[k] ? res : (s[r - 1] - s[l]) * a[k];
        }
        st.push(i);
    }
    cout << res << endl;
    return 0;
}